{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Falling Squares"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #segment-tree #array #ordered-set"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #线段树 #数组 #有序集合"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: fallingSquares"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #掉落的方块"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>在二维平面上的 x 轴上，放置着一些方块。</p>\n",
    "\n",
    "<p>给你一个二维整数数组 <code>positions</code> ，其中 <code>positions[i] = [left<sub>i</sub>, sideLength<sub>i</sub>]</code> 表示：第 <code>i</code> 个方块边长为 <code>sideLength<sub>i</sub></code> ，其左侧边与 x 轴上坐标点&nbsp;<code>left<sub>i</sub></code> 对齐。</p>\n",
    "\n",
    "<p>每个方块都从一个比目前所有的落地方块更高的高度掉落而下。方块沿 y 轴负方向下落，直到着陆到 <strong>另一个正方形的顶边</strong> 或者是 <strong>x 轴上</strong> 。一个方块仅仅是擦过另一个方块的左侧边或右侧边不算着陆。一旦着陆，它就会固定在原地，无法移动。</p>\n",
    "\n",
    "<p>在每个方块掉落后，你必须记录目前所有已经落稳的 <strong>方块堆叠的最高高度</strong> 。</p>\n",
    "\n",
    "<p>返回一个整数数组 <code>ans</code> ，其中 <code>ans[i]</code> 表示在第 <code>i</code> 块方块掉落后堆叠的最高高度。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/04/28/fallingsq1-plane.jpg\" style=\"width: 500px; height: 505px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>positions = [[1,2],[2,3],[6,1]]\n",
    "<strong>输出：</strong>[2,5,5]\n",
    "<strong>解释：</strong>\n",
    "第 1 个方块掉落后，最高的堆叠由方块 1 组成，堆叠的最高高度为 2 。\n",
    "第 2 个方块掉落后，最高的堆叠由方块 1 和 2 组成，堆叠的最高高度为 5 。\n",
    "第 3 个方块掉落后，最高的堆叠仍然由方块 1 和 2 组成，堆叠的最高高度为 5 。\n",
    "因此，返回 [2, 5, 5] 作为答案。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>positions = [[100,100],[200,100]]\n",
    "<strong>输出：</strong>[100,100]\n",
    "<strong>解释：</strong>\n",
    "第 1 个方块掉落后，最高的堆叠由方块 1 组成，堆叠的最高高度为 100 。\n",
    "第 2 个方块掉落后，最高的堆叠可以由方块 1 组成也可以由方块 2 组成，堆叠的最高高度为 100 。\n",
    "因此，返回 [100, 100] 作为答案。\n",
    "注意，方块 2 擦过方块 1 的右侧边，但不会算作在方块 1 上着陆。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= positions.length &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= left<sub>i</sub> &lt;= 10<sup>8</sup></code></li>\n",
    "\t<li><code>1 &lt;= sideLength<sub>i</sub> &lt;= 10<sup>6</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [falling-squares](https://leetcode.cn/problems/falling-squares/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [falling-squares](https://leetcode.cn/problems/falling-squares/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,2],[2,3],[6,1]]', '[[100,100],[200,100]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fallingSquares(self, positions: List[List[int]]) -> List[int]:\n",
    "        ans = []\n",
    "        res = []\n",
    "        for i in range(len(positions)):\n",
    "            left = positions[i][0]\n",
    "            length = positions[i][1]\n",
    "            if not ans:\n",
    "                ans.append(length)\n",
    "                res.append(length)\n",
    "                continue\n",
    "            right = left+length\n",
    "            flag = True\n",
    "            a = 0\n",
    "            for j in range(i):\n",
    "                if left < positions[j][0]+positions[j][1] and positions[j][0] < right:\n",
    "                    flag = False\n",
    "                    a = max(a,res[j]+length)\n",
    "                    continue\n",
    "            if not flag:\n",
    "                res.append(a)\n",
    "                if a > max(ans):\n",
    "                    ans.append(a)\n",
    "                else:\n",
    "                    ans.append(max(ans))\n",
    "                    \n",
    "            if flag:\n",
    "                res.append(length)\n",
    "                ans.append(max(max(ans),length))\n",
    "        return ans\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fallingSquares(self, positions: List[List[int]]) -> List[int]:\n",
    "        n = len(positions)\n",
    "        val = {}\n",
    "        res = [0]\n",
    "        for i in range(n):\n",
    "            l,r = positions[i][0],positions[i][0]+positions[i][1]\n",
    "            hmax = 0\n",
    "            for j in range(i):\n",
    "                if r<=positions[j][0] or l>=positions[j][0]+positions[j][1]:\n",
    "                    continue\n",
    "                hmax = max(hmax,val[j])\n",
    "            tmp = hmax+positions[i][1]\n",
    "            res.append(max(tmp,res[-1]))\n",
    "            val[i] = tmp\n",
    "        return res[1:]\n",
    "\n",
    "             \n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "  def fallingSquares(self, positions):\n",
    "      res = []\n",
    "      ans = []\n",
    "      max_h = 0\n",
    "      for x,y in positions:\n",
    "       pre_h = 0 #着陆最高位置高度\n",
    "       for x1,y1,h in ans:\n",
    "        if not (x1 + y1 <= x or x + y <= x1):\n",
    "         pre_h = max(pre_h,h)\n",
    "       max_h = max(max_h,y + pre_h)\n",
    "       res.append(max_h)\n",
    "       ans.append((x,y,y+pre_h))\n",
    "      return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fallingSquares(self, positions: List[List[int]]) -> List[int]:\n",
    "        ps, hs, res, maxtop = [-sys.maxsize, sys.maxsize], [0], [], 0\n",
    "        for l,h in positions:\n",
    "            r = l+h\n",
    "            li, ri = bisect_right(ps, l),  bisect_left(ps, r)\n",
    "            top = (max(hs[li-1:ri]) if li < ri else hs[li-1]) + h\n",
    "            ps = ps[:li] + [l, r] + ps[ri:] \n",
    "            hs = hs[:li] + [top] + hs[ri-1:]\n",
    "            maxtop = max(maxtop, top)\n",
    "            res.append(maxtop)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fallingSquares(self, positions: List[List[int]]) -> List[int]:\n",
    "        n = len(positions)\n",
    "        val = {}\n",
    "        res = [0]\n",
    "        for i in range(n):\n",
    "            l,r = positions[i][0],positions[i][0]+positions[i][1]\n",
    "            hmax = 0\n",
    "            for j in range(i):\n",
    "                if r<=positions[j][0] or l>=positions[j][0]+positions[j][1]:\n",
    "                    continue\n",
    "                hmax = max(hmax,val[j])\n",
    "            tmp = hmax+positions[i][1]\n",
    "            res.append(max(tmp,res[-1]))\n",
    "            val[i] = tmp\n",
    "        return res[1:]\n",
    "\n",
    "             \n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "  def fallingSquares(self, positions):\n",
    "      res = []\n",
    "      ans = []\n",
    "      max_h = 0\n",
    "      for x,y in positions:\n",
    "       pre_h = 0 #着陆最高位置高度\n",
    "       for x1,y1,h in ans:\n",
    "        if not (x1 + y1 <= x or x + y <= x1):\n",
    "         pre_h = max(pre_h,h)\n",
    "       max_h = max(max_h,y + pre_h)\n",
    "       res.append(max_h)\n",
    "       ans.append((x,y,y+pre_h))\n",
    "      return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def fallingSquares(self, positions: List[List[int]]) -> List[int]:\n",
    "        S = [0] * positions.__len__()\n",
    "        ans = [0] * positions.__len__()\n",
    "        mx = 0\n",
    "\n",
    "        for i, (left, length) in enumerate(positions):\n",
    "            h = 0\n",
    "            for j in range(0, i):\n",
    "                left_, length_ = positions[j]\n",
    "                if (left+length > left_ and left < left_ + length_) or (left+length > left_ and left < left_ + length_):\n",
    "                    h = max(h, S[j])\n",
    "            S[i] = h + length\n",
    "            mx = max(mx, S[i])\n",
    "            ans[i] = mx\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fallingSquares(self, positions: List[List[int]]) -> List[int]:\n",
    "        # 除了线段树这种处理区间的做法外的其它常规做法\n",
    "        # 暴力枚举  ---- 时间复杂度为O(n ** 2)\n",
    "        # 思路: 遍历 positions 如果下一个方块的能堆叠在前几个方块中\n",
    "        # 那么这个方块范围 i 的最高高度是由前几个方块的 最高高度决定的\n",
    "        # height[i] 的初始值就为 add\n",
    "        # height[i] = max(height[i], add + height[j])\n",
    "\n",
    "        n = len(positions)\n",
    "        height = [0] * n\n",
    "        res = []\n",
    "        for i, (left, add) in enumerate(positions):\n",
    "            height[i] = add\n",
    "            right = left + add\n",
    "            for j in range(i):\n",
    "                # 右比左大， 左比右小。 一定在这个上面\n",
    "                if right > positions[j][0] and left < positions[j][1] + positions[j][0]:\n",
    "                    height[i] = max(height[i], add + height[j])\n",
    "            res.append(max(height))\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fallingSquares(self, positions: List[List[int]]) -> List[int]:\n",
    "        n=len(positions)\n",
    "        dp=[0]*n\n",
    "        for i,(l,h) in enumerate(positions):\n",
    "            r=l+h\n",
    "            dp[i]=h\n",
    "            for j in range(i):\n",
    "                l1=positions[j][0]\n",
    "                r1=positions[j][0]+positions[j][1]\n",
    "               #print(l,r,l1,r1)\n",
    "                if r>l1 and r1>l:\n",
    "                    dp[i]=max(dp[i],dp[j]+h)\n",
    "        for i in range(1,n):\n",
    "            dp[i]=max(dp[i-1],dp[i])\n",
    "        return dp\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fallingSquares(self, positions: List[List[int]]) -> List[int]:\n",
    "    \n",
    "        n = len(positions)\n",
    "        heights = [0] * n\n",
    "        ans = []\n",
    "\n",
    "        for i in range(n):\n",
    "            left, sideLength = positions[i]\n",
    "            right = left + sideLength\n",
    "            height = sideLength\n",
    "\n",
    "            for j in range(i):\n",
    "                l, s = positions[j]\n",
    "                r = l + s\n",
    "                if left < r and right > l:\n",
    "                    height = max(height, heights[j] + sideLength)\n",
    "\n",
    "            heights[i] = height\n",
    "            ans.append(max(ans[-1], height) if ans else height)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fallingSquares(self, positions: List[List[int]]) -> List[int]:\n",
    "        res = []\n",
    "        ans = []\n",
    "        max_height = 0\n",
    "        for x,y in positions:\n",
    "            cur = 0\n",
    "            for a,b,h in ans:\n",
    "                if not (a + b <= x or x + y <= a ):\n",
    "                    cur = max(cur,h)\n",
    "            max_height = max(max_height,y + cur)\n",
    "            res.append(max_height)\n",
    "            ans.append([x,y,y+cur])\n",
    "        return res    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fallingSquares(self, positions: List[List[int]]) -> List[int]:\n",
    "        n = len(positions)\n",
    "        heights = [0] * n\n",
    "        for i, (left1, side1) in enumerate(positions):\n",
    "            right1 = left1 + side1 - 1\n",
    "            heights[i] = side1\n",
    "            for j in range(i):\n",
    "                left2, right2 = positions[j][0], positions[j][0] + positions[j][1] - 1\n",
    "                if right1 >= left2 and right2 >= left1:\n",
    "                    heights[i] = max(heights[i], heights[j] + side1)\n",
    "        for i in range(1, n):\n",
    "            heights[i] = max(heights[i], heights[i - 1])\n",
    "        return heights\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def fallingSquares(self, positions: List[List[int]]) -> List[int]:\r\n",
    "        heights=[pos[1] for pos in positions]\r\n",
    "        for i in range(1,len(positions)):\r\n",
    "            upper_left,upper_side=positions[i]\r\n",
    "            upper_right=upper_side+upper_left\r\n",
    "            for j in range(i):\r\n",
    "                lower_left,lower_side=positions[j]\r\n",
    "                lower_right=lower_left+lower_side\r\n",
    "                if not (lower_right<=upper_left or lower_left>=upper_right):\r\n",
    "                    heights[i]=max(heights[i],heights[j]+upper_side)\r\n",
    "        \r\n",
    "        Max=heights[0]\r\n",
    "        for i in range(1,len(heights)):\r\n",
    "            if heights[i]>Max:\r\n",
    "                Max=heights[i]\r\n",
    "            else:\r\n",
    "                heights[i]=Max\r\n",
    "        return heights\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fallingSquares(self, positions: List[List[int]]) -> List[int]:\n",
    "        n = len(positions)\n",
    "        heights = [0] * n\n",
    "        for i, (left1, side1) in enumerate(positions):\n",
    "            right1 = left1 + side1 - 1\n",
    "            heights[i] = side1\n",
    "            for j in range(i):\n",
    "                left2, right2 = positions[j][0], positions[j][0] + positions[j][1] - 1\n",
    "                if right1 >= left2 and right2 >= left1:\n",
    "                    heights[i] = max(heights[i], heights[j] + side1)\n",
    "        for i in range(1, n):\n",
    "            heights[i] = max(heights[i], heights[i - 1])\n",
    "        return heights\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fallingSquares(self, positions: List[List[int]]) -> List[int]:\n",
    "        ans = []\n",
    "        res = []\n",
    "        for i in range(len(positions)):\n",
    "            left = positions[i][0]\n",
    "            length = positions[i][1]\n",
    "            if not ans:\n",
    "                ans.append(length)\n",
    "                res.append(length)\n",
    "                continue\n",
    "            right = left+length\n",
    "            flag = True\n",
    "            a = 0\n",
    "            for j in range(i):\n",
    "                if left < positions[j][0]+positions[j][1] and positions[j][0] < right:\n",
    "                    flag = False\n",
    "                    a = max(a,res[j]+length)\n",
    "                    continue\n",
    "            if not flag:\n",
    "                res.append(a)\n",
    "                if a > max(ans):\n",
    "                    ans.append(a)\n",
    "                else:\n",
    "                    ans.append(max(ans))\n",
    "                    \n",
    "            if flag:\n",
    "                res.append(length)\n",
    "                ans.append(max(max(ans),length))\n",
    "        return ans\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fallingSquares(self, positions: List[List[int]]) -> List[int]:\n",
    "        n = len(positions)\n",
    "        heights = [0] * n\n",
    "        for i, (left1, side1) in enumerate(positions):\n",
    "            right1 = left1 + side1 - 1\n",
    "            heights[i] = side1\n",
    "            for j in range(i):\n",
    "                left2, right2 = positions[j][0], positions[j][0] + positions[j][1] - 1\n",
    "                if right1 >= left2 and right2 >= left1:\n",
    "                    heights[i] = max(heights[i], heights[j] + side1)\n",
    "        for i in range(1, n):\n",
    "            heights[i] = max(heights[i], heights[i - 1])\n",
    "        return heights\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fallingSquares(self, positions: List[List[int]]) -> List[int]:\n",
    "        # 除了线段树这种处理区间的做法外的其它常规做法\n",
    "        # 暴力枚举  ---- 时间复杂度为O(n ** 2)\n",
    "        # 思路: 遍历 positions 如果下一个方块的能堆叠在前几个方块中\n",
    "        # 那么这个方块范围 i 的最高高度是由前几个方块的 最高高度决定的\n",
    "        # height[i] 的初始值就为 add\n",
    "        # height[i] = max(height[i], add + height[j])\n",
    "\n",
    "        n = len(positions)\n",
    "        height = [0] * n\n",
    "        res = []\n",
    "        for i, (left, add) in enumerate(positions):\n",
    "            height[i] = add\n",
    "            right = left + add\n",
    "            for j in range(i):\n",
    "                # 右比左大， 左比右小。 一定在这个上面\n",
    "                if right > positions[j][0] and left < positions[j][1] + positions[j][0]:\n",
    "                    height[i] = max(height[i], add + height[j])\n",
    "            res.append(max(height))\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fallingSquares(self, positions: List[List[int]]) -> List[int]:\n",
    "        ans = []\n",
    "        res = []\n",
    "        for i in range(len(positions)):\n",
    "            left = positions[i][0]\n",
    "            length = positions[i][1]\n",
    "            if not ans:\n",
    "                ans.append(length)\n",
    "                res.append(length)\n",
    "                continue\n",
    "            right = left+length\n",
    "            flag = True\n",
    "            a = 0\n",
    "            for j in range(i):\n",
    "                if left < positions[j][0]+positions[j][1] and positions[j][0] < right:\n",
    "                    flag = False\n",
    "                    a = max(a,res[j]+length)\n",
    "                    continue\n",
    "            if not flag:\n",
    "                res.append(a)\n",
    "                if a > max(ans):\n",
    "                    ans.append(a)\n",
    "                else:\n",
    "                    ans.append(max(ans))\n",
    "                    \n",
    "            if flag:\n",
    "                res.append(length)\n",
    "                ans.append(max(max(ans),length))\n",
    "        return ans\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def get_pos(start, store):\n",
    "    for i, (_, right, _) in enumerate(store):\n",
    "        if start < right:\n",
    "            return i\n",
    "    return len(store)\n",
    "\n",
    "def add_one_block(left, length, store):\n",
    "    pos = get_pos(left, store)\n",
    "\n",
    "    right = left + length\n",
    "    min_h = 0\n",
    "    if pos < len(store):\n",
    "        l1, r1, h1 = store[pos]\n",
    "        if l1 < left:   # 前面需要拆分:\n",
    "            store[pos] = (l1, left, h1)\n",
    "            if r1 > right:\n",
    "                store[pos+1:pos+1] = [(right, r1, h1)]           \n",
    "            pos += 1\n",
    "            min_h = h1\n",
    "\n",
    "    for i in range(pos, len(store)):\n",
    "        l1, r1, h1 = store[i]\n",
    "        if l1 >= right:\n",
    "            endpos = i\n",
    "            break\n",
    "        if r1 > right:\n",
    "            min_h = max(min_h, h1)\n",
    "            store[i] = (right,r1,h1)\n",
    "            endpos = i\n",
    "            break\n",
    "        min_h = max(min_h, h1)\n",
    "    else:\n",
    "        endpos = len(store)\n",
    "\n",
    "    store[pos:endpos] = [(left, right, length + min_h)]\n",
    "    return length + min_h\n",
    "\n",
    "class Solution(object):\n",
    "    def fallingSquares(self, positions):\n",
    "        store = []\n",
    "        res = []\n",
    "        maxh = 0\n",
    "        for left, length in positions:\n",
    "            maxh = max(maxh, add_one_block(left, length, store))\n",
    "            res.append(maxh)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def fallingSquares(self, positions):\n",
    "        res = []\n",
    "        ans = []\n",
    "        max_h = 0\n",
    "        for x,y in positions:\n",
    "            pre_h = 0 #着陆最高位置高度\n",
    "            for x1,y1,h in ans:\n",
    "                if not (x1 + y1 <= x or x + y <= x1):\n",
    "                    pre_h = max(pre_h,h)\n",
    "            max_h = max(max_h,y + pre_h)\n",
    "            res.append(max_h)\n",
    "            ans.append((x,y,y+pre_h))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fallingSquares(self, positions: List[List[int]]) -> List[int]:\n",
    "        res = []\n",
    "        ans = []\n",
    "        max_height = 0\n",
    "        for x,y in positions:\n",
    "            cur = 0\n",
    "            for a,b,h in ans:\n",
    "                if not (a + b <= x or x + y <= a ):\n",
    "                    cur = max(cur,h)\n",
    "            max_height = max(max_height,y + cur)\n",
    "            res.append(max_height)\n",
    "            ans.append((x,y,y+cur))\n",
    "        return res    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fallingSquares(self, positions: List[List[int]]) -> List[int]:\n",
    "        ps, hs, res, maxtop = [-sys.maxsize, sys.maxsize], [0], [], 0\n",
    "        for l,h in positions:\n",
    "            r = l+h\n",
    "            li, ri = bisect_right(ps, l),  bisect_left(ps, r)\n",
    "            top = (max(hs[li-1:ri]) if li < ri else hs[li-1]) + h\n",
    "            ps = ps[:li] + [l, r] + ps[ri:] \n",
    "            hs = hs[:li] + [top] + hs[ri-1:]\n",
    "            maxtop = max(maxtop, top)\n",
    "            res.append(maxtop)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def fallingSquares(self, positions: List[List[int]]) -> List[int]:\n",
    "        S = [0] * positions.__len__()\n",
    "        ans = [0] * positions.__len__()\n",
    "        mx = 0\n",
    "\n",
    "        for i, (left, length) in enumerate(positions):\n",
    "            h = 0\n",
    "            for j in range(0, i):\n",
    "                left_, length_ = positions[j]\n",
    "                if (left+length > left_ and left < left_ + length_) or (left+length > left_ and left < left_ + length_):\n",
    "                    h = max(h, S[j])\n",
    "            S[i] = h + length\n",
    "            mx = max(mx, S[i])\n",
    "            ans[i] = mx\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fallingSquares(self, positions: List[List[int]]) -> List[int]:\n",
    "        n = len(positions)\n",
    "        heights = [0] * n\n",
    "        for i,(left1,side1) in enumerate(positions):\n",
    "            right1 = left1 + side1 - 1\n",
    "            heights[i] = side1\n",
    "            for j in range(i):\n",
    "                left2,right2 = positions[j][0],positions[j][0] + positions[j][1] - 1\n",
    "                if right1 >= left2 and left1 <= right2:\n",
    "                    heights[i] = max(heights[i],heights[j] + side1)\n",
    "        for i in range(1, n):\n",
    "            heights[i] = max(heights[i], heights[i - 1])\n",
    "        return heights"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fallingSquares(self, positions: List[List[int]]) -> List[int]:\n",
    "        n = len(positions)\n",
    "        heights = [0] * n\n",
    "        for i, (left1, side1) in enumerate(positions):\n",
    "            right1 = left1 + side1 - 1\n",
    "            heights[i] = side1\n",
    "            for j in range(i):\n",
    "                left2, right2 = positions[j][0], positions[j][0] + positions[j][1] - 1\n",
    "                if right1 >= left2 and right2 >= left1:\n",
    "                    heights[i] = max(heights[i], heights[j] + side1)\n",
    "        for i in range(1, n):\n",
    "            heights[i] = max(heights[i], heights[i - 1])\n",
    "        return heights\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def get_pos(start, store):\n",
    "    for i, (_, right, _) in enumerate(store):\n",
    "        if start < right:\n",
    "            return i\n",
    "    return len(store)\n",
    "\n",
    "def add_one_block(left, length, store):\n",
    "    pos = get_pos(left, store)\n",
    "\n",
    "    right = left + length\n",
    "    min_h = 0\n",
    "    if pos < len(store):\n",
    "        l1, r1, h1 = store[pos]\n",
    "        if l1 < left:   # 前面需要拆分:\n",
    "            store[pos] = (l1, left, h1)\n",
    "            if r1 > right:\n",
    "                store[pos+1:pos+1] = [(right, r1, h1)]           \n",
    "            pos += 1\n",
    "            min_h = h1\n",
    "\n",
    "    for i in range(pos, len(store)):\n",
    "        l1, r1, h1 = store[i]\n",
    "        if l1 >= right:\n",
    "            endpos = i\n",
    "            break\n",
    "        if r1 > right:\n",
    "            min_h = max(min_h, h1)\n",
    "            store[i] = (right,r1,h1)\n",
    "            endpos = i\n",
    "            break\n",
    "        min_h = max(min_h, h1)\n",
    "    else:\n",
    "        endpos = len(store)\n",
    "\n",
    "    store[pos:endpos] = [(left, right, length + min_h)]\n",
    "    return length + min_h\n",
    "\n",
    "class Solution(object):\n",
    "    def fallingSquares(self, positions):\n",
    "        store = []\n",
    "        res = []\n",
    "        maxh = 0\n",
    "        for left, length in positions:\n",
    "            maxh = max(maxh, add_one_block(left, length, store))\n",
    "            res.append(maxh)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fallingSquares(self: any, positions: list) -> list:\n",
    "        self.position_hight = [(-float(\"Inf\"), float(\"Inf\"), 0)]\n",
    "        all_max_high = 0\n",
    "        res = []\n",
    "\n",
    "        for p in positions:\n",
    "            nl = p[0]\n",
    "            nr = p[0] + p[1] - 1\n",
    "\n",
    "            li = self.bi_find(0, len(self.position_hight) - 1, nl)\n",
    "            ri = self.bi_find(0, len(self.position_hight) - 1, nr)\n",
    "\n",
    "            new_dis, max_high = self.split_distence(li, ri, nl, nr, p[1])\n",
    "            self.position_hight[li:ri+1] = new_dis\n",
    "            all_max_high = max(all_max_high, max_high)\n",
    "\n",
    "            #print(self.position_hight)\n",
    "            res.append(all_max_high)\n",
    "\n",
    "        return res\n",
    "\n",
    "    def bi_find(self: any, start: int, end: int, v: int) -> int:\n",
    "        mid = (start + end) // 2\n",
    "\n",
    "        if self.position_hight[mid][0] <= v <= self.position_hight[mid][1]:\n",
    "            return mid\n",
    "        elif v < self.position_hight[mid][0]:\n",
    "            return self.bi_find(start, mid - 1, v)\n",
    "        else:\n",
    "            return self.bi_find(mid + 1, end, v)\n",
    "\n",
    "    def split_distence(self: any, li: int, ri:int, nl: int, nr: int, nh: int) -> list:\n",
    "        max_high = max(h[2] for h in self.position_hight[li:ri+1]) + nh\n",
    "        new_dis = []\n",
    "\n",
    "        if nl-1 >= self.position_hight[li][0]:\n",
    "            new_dis.append((self.position_hight[li][0], nl-1, self.position_hight[li][2]))\n",
    "\n",
    "        new_dis.append((nl, nr, max_high))\n",
    "\n",
    "        if nr+1 <= self.position_hight[ri][1]:\n",
    "            new_dis.append((nr+1, self.position_hight[ri][1], self.position_hight[ri][2]))\n",
    "\n",
    "        return new_dis, max_high"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def get_pos(start, store):\n",
    "    for i, (_, right, _) in enumerate(store):\n",
    "        if start < right:\n",
    "            return i\n",
    "    return len(store)\n",
    "\n",
    "def add_one_block(left, length, store):\n",
    "    pos = get_pos(left, store)\n",
    "\n",
    "    right = left + length\n",
    "    min_h = 0\n",
    "    if pos < len(store):\n",
    "        l1, r1, h1 = store[pos]\n",
    "        if l1 < left:   # 前面需要拆分:\n",
    "            store[pos] = (l1, left, h1)\n",
    "            if r1 > right:\n",
    "                store[pos+1:pos+1] = [(right, r1, h1)]\n",
    "            pos += 1\n",
    "            min_h = h1\n",
    "\n",
    "    for i in range(pos, len(store)):\n",
    "        l1, r1, h1 = store[i]\n",
    "        if l1 >= right:\n",
    "            endpos = i\n",
    "            break\n",
    "        if r1 > right:\n",
    "            min_h = max(min_h, h1)\n",
    "            store[i] = (right, r1, h1)\n",
    "            endpos = i\n",
    "            break\n",
    "        min_h = max(min_h, h1)\n",
    "    else:\n",
    "        endpos = len(store)\n",
    "\n",
    "    store[pos:endpos] = [(left, right, length + min_h)]\n",
    "    return length + min_h\n",
    "\n",
    "class Solution(object):\n",
    "    def fallingSquares(self, positions):\n",
    "        store = []\n",
    "        res = []\n",
    "        maxh = 0\n",
    "        for left, length in positions:\n",
    "            maxh = max(maxh, add_one_block(left, length, store))\n",
    "            res.append(maxh)\n",
    "        return res\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fallingSquares(self, positions: List[List[int]]) -> List[int]:\n",
    "        n = len(positions)\n",
    "        heights = [0]*n\n",
    "        for i, (left1,side1) in enumerate(positions):\n",
    "            right1 = left1 + side1 - 1\n",
    "            heights[i] = side1\n",
    "            for j in range(i):\n",
    "                left2, right2 = positions[j][0], positions[j][0]+positions[j][1]-1\n",
    "                if right1 >= left2 and right2>=left1:\n",
    "                    heights[i] = max(heights[i], heights[j]+side1)\n",
    "        for i in range(1, n):\n",
    "            heights[i] = max(heights[i], heights[i-1])\n",
    "        return heights\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fallingSquares(self, positions: List[List[int]]) -> List[int]:\n",
    "        n=len(positions)\n",
    "        heights=[0]*n\n",
    "\n",
    "        #得到的是目前落下的位置的高度\n",
    "        for i, (left,side) in enumerate(positions):\n",
    "            right=left+side-1   #擦过去不算重合\n",
    "            heights[i]=side\n",
    "\n",
    "            for j in range(i):\n",
    "                l,r=positions[j][0],positions[j][0]+positions[j][1]-1\n",
    "                if right>=l and r>=left:\n",
    "                    heights[i]=max(heights[j]+side,heights[i])\n",
    "        \n",
    "        for i in range(1,n):\n",
    "            heights[i]=max(heights[i-1],heights[i])\n",
    "        \n",
    "        return heights"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fallingSquares(self, positions: List[List[int]]) -> List[int]:\n",
    "        n = len(positions)\n",
    "        height = [0] * n\n",
    "        height[0] = positions[0][1]\n",
    "        for i in range(1, n):\n",
    "            left, right = positions[i][0], positions[i][0] + positions[i][1]\n",
    "            height[i] = positions[i][1]\n",
    "            for j in range(i):\n",
    "                left_j, right_j = positions[j][0], positions[j][0] + positions[j][1]\n",
    "                if left >= right_j or right <= left_j:\n",
    "                    continue\n",
    "                height[i] = max(height[i], height[j] + positions[i][1])\n",
    "\n",
    "        for i in range(1, n):\n",
    "            height[i] = max(height[i], height[i - 1])\n",
    "\n",
    "        return height\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fallingSquares(self, positions: List[List[int]]) -> List[int]:\n",
    "        # 对于示例一 我们发现 其在区间[1, 2] 上的值应该是 2\n",
    "        #                      在区间[2, 5] 上的值应该是 5\n",
    "        #                      在区间[6, 7] 上的值应该是 1\n",
    "        # 一下子就想到了 线段树\n",
    "\n",
    "        # n 是 总共 的节点个数\n",
    "        # 因为数据比较大 不太可能用最大值来充当 n\n",
    "        # 那么我们就可以用一个去了重的列表 或者是一个 有序集合 来表示\n",
    "        # 我们的 l 与 r 的定义就是 列表内的索引值 将索引值当成是区间， 就能把区间内的\n",
    "        # 节点个数的最大值 降至 1000\n",
    "\n",
    "        # 返回的是每一次操作后的堆叠的最高高度 因此不用写 build 方法\n",
    "        # 我们观察到 在 示例一 3 ~ 5 这个范围内 它的值 应该是 5 而不是 3\n",
    "        # 因此 这道题就不是简单的区间 分割了 应该要提供一个查询方法 来查询 区间内的最大值\n",
    "        # 累加的值 也应该是这个最大值 + 边长。\n",
    "        \n",
    "        # 我们每次的更新操作会使区间块破坏 向下走，如果我们要统计某个区间的最大值，那先匹配到的一定是上面符合的位置，而不是下面符合的位置，如果我们全部都遍历的话，那么时间复杂度就会近似于暴力了，因此我们需要一个数组来对区间上面部分进行维护\n",
    "\n",
    "        # 在本题中 是不可能出现 L == R 的情况的\n",
    "\n",
    "        def broke_it(o:int):\n",
    "            if message_l[o] != 0:\n",
    "                max_message_l[o * 2] = max_message_l[o]\n",
    "                max_message_l[o * 2 + 1] = max_message_l[o] \n",
    "                message_l[o*2] = message_l[o]\n",
    "                message_l[o*2+1] = message_l[o]\n",
    "                message_l[o] = 0\n",
    "\n",
    "\n",
    "        # 区间查询的代码  ----- 返回的是该区间内的最大值\n",
    "        def query(o:int, l:int, r:int, L:int, R:int) -> int:\n",
    "            s = 0\n",
    "            if l > R or r < L:\n",
    "                return 0\n",
    "            if L <= l and r <= R:  # 我们找到了这个区间\n",
    "                return max_message_l[o]\n",
    "            mid = (l + r) // 2\n",
    "            # 一定会存在区间破坏情况\n",
    "            broke_it(o)\n",
    "            if mid >= L: s = max(s, query(o*2, l, mid, L, R))\n",
    "            if mid < R: s = max(s, query(o*2+1, mid+1, r, L, R))\n",
    "            return s\n",
    "\n",
    "        \n",
    "        # 区间更新的代码 ------ 这里是执行区间上的更新操作（注意维护最大区间信息）\n",
    "        def update(o:int, l:int, r:int, L:int, R:int, val:int) -> None:\n",
    "            if l > R or r < L:\n",
    "                return \n",
    "            if L <= l and r <= R:  # 我们找到了这个区间\n",
    "                message_l[o] = val\n",
    "                max_message_l[o] = val\n",
    "                return\n",
    "            mid = (l + r) // 2\n",
    "            # 一定会存在区间破坏情况\n",
    "            broke_it(o)\n",
    "            if mid >= L: update(o*2, l, mid, L, R, val)\n",
    "            if mid < R: update(o*2+1, mid+1, r, L, R, val)\n",
    "            # 维护最大区间信息\n",
    "            max_message_l[o] = max(max_message_l[o*2], max_message_l[o* 2 + 1]) \n",
    "\n",
    "\n",
    "        # 首先写初始化部分的代码\n",
    "        # 左端点和右端点的总共数量 ----- 我们用索引来表示区间上的点\n",
    "        lst = [i for i, _ in positions] + [i + v for i, v in positions]\n",
    "        lst = list(set(lst))  # 去重处理\n",
    "        # 后面要查找每个区间的位置就需要顺序，因此要排个序\n",
    "        lst.sort()\n",
    "        n = len(lst)\n",
    "        # 初始化两个数组 \n",
    "        # 一个数组记录区间的信息， 一个数组维护区间的最大值\n",
    "        message_l = [0] * (4 * n)  # 开一个大小为 4n 的空间\n",
    "        max_message_l = [0] *(4 * n)\n",
    "\n",
    "        # 储存结果的列表\n",
    "        res = []\n",
    "\n",
    "        for left, add in positions:\n",
    "            right = left + add\n",
    "            l = bisect.bisect_left(lst, left)\n",
    "            r = bisect.bisect_left(lst, right)\n",
    "            # 进行查询操作，查询该区间上的最大值\n",
    "            # 因为我们的区间的起始值设置了 1 所以我们传入的 l 应该 +1 处理\n",
    "            add += query(1, 1, n, l+1, r)\n",
    "            update(1, 1, n, l+1, r, add)\n",
    "            res.append(max_message_l[1])  # 最大信息肯定是维护在第一个上的\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fallingSquares(self, positions: List[List[int]]) -> List[int]:\n",
    "        def lt699_2(blocks):\n",
    "            n = len(blocks)\n",
    "            cuts = []\n",
    "            for block in blocks:\n",
    "                cuts.append(block[0])\n",
    "                cuts.append(block[0] + block[1])\n",
    "            cuts = list(set(cuts))\n",
    "            cuts.sort()\n",
    "            n_cuts = len(cuts)\n",
    "            c=[0]*(n_cuts-1)\n",
    "            def get(l,r):\n",
    "                i=cuts.index(l)\n",
    "                j=i\n",
    "                while cuts[j]!=r:j+=1\n",
    "                return i,j\n",
    "            def update(i,j,h):\n",
    "                for k in range(i,j):c[k]=h\n",
    "            def query(i,j):\n",
    "                return max(c[i:j])\n",
    "\n",
    "            res=[]\n",
    "            for block in blocks:\n",
    "                i,j=get(block[0],block[0]+block[1])\n",
    "                h=block[1]\n",
    "                h+=query(i,j)\n",
    "                update(i,j,h)\n",
    "                res.append(query(0,n_cuts))\n",
    "            return res\n",
    "        return lt699_2(positions)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchl(self, l, r, t):\n",
    "        if l > r:\n",
    "            return r\n",
    "        m = (l+r)//2\n",
    "        if self.h[m][0] > t:\n",
    "            return self.searchl(l, m-1, t)\n",
    "        return self.searchl(m+1, r, t)\n",
    "\n",
    "    def searchr(self, l, r, t):\n",
    "        if l > r:\n",
    "            return r\n",
    "        m = (l+r)//2\n",
    "        if self.h[m][0] < t:\n",
    "            return self.searchr(m+1, r, t)\n",
    "        return self.searchr(l, m-1, t)\n",
    "\n",
    "    def fallingSquares(self, positions: List[List[int]]) -> List[int]:\n",
    "        self.h = h = [[0, 0]]\n",
    "\n",
    "        ret = []\n",
    "        k = 0\n",
    "        for i in range(len(positions)):\n",
    "            l = self.searchl(0, len(h)-1, positions[i][0])\n",
    "            r = self.searchr(0, len(h)-1, positions[i][0]+positions[i][1])\n",
    "\n",
    "            m = max(0, *[j[1] for j in h[l:r+1]])\n",
    "            self.h = h = h[:l+1] + [[positions[i][0],m+positions[i][1]], [positions[i][0]+positions[i][1],h[r][1]]] + h[r+1:]\n",
    "            if l+3 < len(h) and positions[i][0]+positions[i][1] == h[l+3][0]:\n",
    "                h[l+2][1] = max(h[l+2][1], h[l+3][1])\n",
    "                h.pop(l+3)\n",
    "                if l+3 < len(h) and h[l+2][1] == h[l+3][1]:\n",
    "                    h.pop(l+3)\n",
    "            if positions[i][0] == h[l][0]:\n",
    "                h[l+1][1] = max(h[l][1], h[l+1][1])\n",
    "                h.pop(l)\n",
    "                if h[l-1][1] == h[l][1]:\n",
    "                    h.pop(l)\n",
    "\n",
    "            k = max(k, m+positions[i][1])\n",
    "            ret.append(k)\n",
    "\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fallingSquares(self, positions: List[List[int]]) -> List[int]:\n",
    "\n",
    "        def push_up(o):\n",
    "            tree[o] = max(tree[o*2], tree[o*2+1])\n",
    "        \n",
    "        def push_down(o):\n",
    "            if lazy[o]:\n",
    "                lazy[o*2] = lazy[o]\n",
    "                lazy[o*2+1] = lazy[o]\n",
    "\n",
    "                tree[o*2] = lazy[o]\n",
    "                tree[o*2+1] = lazy[o]\n",
    "                lazy[o] = 0\n",
    "        \n",
    "        def update(o, l, r, L, R, val):\n",
    "            if l >=L and r <= R:\n",
    "                tree[o] = val\n",
    "                lazy[o] = val\n",
    "                return\n",
    "\n",
    "            mid = (l + r) // 2\n",
    "            push_down(o)\n",
    "            if mid >= L:\n",
    "                update(o*2, l, mid, L, R, val)\n",
    "            if mid+1<=R:\n",
    "                update(o*2+1, mid+1, r, L, R, val)\n",
    "            push_up(o)\n",
    "        \n",
    "        def query(o, l, r, L, R):\n",
    "            if l>=L and r <= R:\n",
    "                return tree[o]\n",
    "            mid = (l + r) // 2\n",
    "            push_down(o)\n",
    "            ans = 0\n",
    "            if mid >= L:\n",
    "                ans = max(ans, query(o*2, l, mid, L, R))\n",
    "            if mid+1<=R:\n",
    "                ans = max(ans, query(o*2+1, mid+1, r, L, R))\n",
    "            return ans\n",
    "        \n",
    "        nums = list()\n",
    "        for l, w in positions:\n",
    "            nums.append(l)\n",
    "            nums.append(l+w-1)\n",
    "        \n",
    "        new_nums = sorted(set(nums))\n",
    "\n",
    "        n = len(new_nums)\n",
    "        tree = [0] * (4*n)\n",
    "        lazy = [0] * (4*n)\n",
    "\n",
    "        ans = []\n",
    "        max_h = 0\n",
    "        for l, w in positions:\n",
    "            r = l + w - 1\n",
    "            i = bisect_left(new_nums, l) + 1\n",
    "            j = bisect_left(new_nums, r) + 1\n",
    "            q = query(1, 1, n, i, j)\n",
    "            h = q + w\n",
    "            max_h = max(max_h, h)\n",
    "            ans.append(max_h)\n",
    "            update(1, 1, n, i, j, h)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList \n",
    "class ODT:\n",
    "    def __init__(self):\n",
    "        self.tree=SortedList()##存储(左端点，右端点，值)\n",
    "\n",
    "    def split(self,pos):\n",
    "        i=bisect_left(self.tree,pos,key=lambda x:x[0])\n",
    "        if i<len(self.tree) and self.tree[i][0]==pos:\n",
    "            return i\n",
    "        if i==0:return 0\n",
    "        left,right,val=self.tree[i-1]\n",
    "        if pos<right:\n",
    "            self.tree[i-1][1]=pos\n",
    "            self.tree.add([pos,right,val])##具体分裂操作需按照实际要求\n",
    "        return i\n",
    "\n",
    "    def assign(self,left,right,val):\n",
    "        begin=self.split(left)\n",
    "        # print(self.tree)\n",
    "        end=self.split(right)\n",
    "        # print(begin,end,self.tree)\n",
    "        base=0\n",
    "        for k in range(begin,end):\n",
    "            tup=self.tree.pop(begin)\n",
    "            base=max(base,tup[2])\n",
    "        val+=base\n",
    "        self.tree.add([left,right,val])\n",
    "        # print(self.tree)\n",
    "        return val\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def fallingSquares(self, positions: List[List[int]]) -> List[int]:\n",
    "        ans=[]\n",
    "        best=0\n",
    "        T=ODT()\n",
    "        for left,size in positions:\n",
    "            size=T.assign(left,left+size,size)\n",
    "            best=max(best,size)\n",
    "            ans.append(best)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class IntervalTree:\n",
    "    def __init__(self, size):\n",
    "        self.size = size\n",
    "        self.interval_tree = [0 for _ in range(size*4)]\n",
    "        self.lazys = [0 for _ in range(size*4)]\n",
    "\n",
    "    def give_lay_to_son(self,p,l,r):\n",
    "        interval_tree = self.interval_tree\n",
    "        lazys = self.lazys\n",
    "        if lazys[p] == 0:\n",
    "            return\n",
    "        mid = (l+r)//2\n",
    "        interval_tree[p*2] = lazys[p]\n",
    "        interval_tree[p*2+1] = lazys[p]\n",
    "        lazys[p*2] = lazys[p]\n",
    "        lazys[p*2+1] = lazys[p]\n",
    "        lazys[p] = 0\n",
    "        \n",
    "    def update(self,p,l,r,x,y,val):\n",
    "        \"\"\"\n",
    "        把[x,y]区域全变成val\n",
    "        \"\"\"\n",
    "        if y < l or r < x:\n",
    "            return \n",
    "        interval_tree = self.interval_tree    \n",
    "        lazys = self.lazys        \n",
    "        if x <= l and r<=y:\n",
    "            interval_tree[p] = val\n",
    "            lazys[p] = val\n",
    "            return\n",
    "        self.give_lay_to_son(p,l,r)\n",
    "        mid = (l+r)//2\n",
    "        if x <= mid:\n",
    "            self.update(p*2,l,mid,x,y,val)\n",
    "        if mid < y:\n",
    "            self.update(p*2+1,mid+1,r,x,y,val)\n",
    "        interval_tree[p] = max(interval_tree[p*2], interval_tree[p*2+1])\n",
    "    \n",
    "    def query(self,p,l,r,x,y):\n",
    "        \"\"\"\n",
    "        查找x,y区间的最大值        \"\"\"        \n",
    "        \n",
    "        if y < l or r < x:\n",
    "            return 0\n",
    "        if x<=l and r<=y:\n",
    "            return self.interval_tree[p]\n",
    "        self.give_lay_to_son(p,l,r)\n",
    "        mid = (l+r)//2\n",
    "        s = 0\n",
    "        if x <= mid:\n",
    "            s = max(s,self.query(p*2,l,mid,x,y))\n",
    "        if mid < y:\n",
    "            s = max(s,self.query(p*2+1,mid+1,r,x,y))\n",
    "        return s\n",
    "\n",
    "class Solution:\n",
    "    def fallingSquares(self, positions: List[List[int]]) -> List[int]:\n",
    "        n = len(positions)\n",
    "        hashes = [left for left,_ in positions] + [left+side for left,side in positions] \n",
    "        hashes = sorted(list(set(hashes)))\n",
    "        # 用线段树维护x轴区间最大值，记录每个点的高度：比如[1,2]这个方块，会使线段[1,2]闭区间这个线段上的每个高度都变成2\n",
    "        # 落下一个新方块时，查询它的底边所在线段[x,y]的最大高度h，这个方块会落在这个高度h，把新高度h+side插入线段树[x,y]的部分\n",
    "        # 每次插入结束，树根存的高度就是当前最大高度\n",
    "        # 由于数据范围大1 <= lefti <= 108，需要散列化\n",
    "        # 散列化的值有left和right(线段短点)\n",
    "        # print(hashes)\n",
    "        tree_size = len(hashes)\n",
    "        tree = IntervalTree(tree_size)\n",
    "        # 离散化\n",
    "        \n",
    "        heights = []\n",
    "        for left,d in positions:\n",
    "            right = left + d \n",
    "            l = bisect_left(hashes,left)\n",
    "            r = bisect_left(hashes,right)\n",
    "            h = tree.query(1,1,tree_size,l+1,r)\n",
    "            tree.update(1,1,tree_size,l+1,r,h+d)\n",
    "            heights.append(tree.interval_tree[1])\n",
    "        return heights\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class IntervalTree:\n",
    "    def __init__(self, size):\n",
    "        self.size = size\n",
    "        self.interval_tree = [0 for _ in range(size*4)]\n",
    "        self.lazys = [0 for _ in range(size*4)]\n",
    "\n",
    "    def give_lay_to_son(self,p,l,r):\n",
    "        interval_tree = self.interval_tree\n",
    "        lazys = self.lazys\n",
    "        if lazys[p] == 0:\n",
    "            return\n",
    "        mid = (l+r)//2\n",
    "        interval_tree[p*2] = lazys[p]\n",
    "        interval_tree[p*2+1] = lazys[p]\n",
    "        lazys[p*2] = lazys[p]\n",
    "        lazys[p*2+1] = lazys[p]\n",
    "        lazys[p] = 0\n",
    "        \n",
    "    def update(self,p,l,r,x,y,val):\n",
    "        \"\"\"\n",
    "        把[x,y]区域全变成val\n",
    "        \"\"\"\n",
    "        if y < l or r < x:\n",
    "            return \n",
    "        interval_tree = self.interval_tree    \n",
    "        lazys = self.lazys        \n",
    "        if x <= l and r<=y:\n",
    "            interval_tree[p] = val\n",
    "            lazys[p] = val\n",
    "            return\n",
    "        self.give_lay_to_son(p,l,r)\n",
    "        mid = (l+r)//2\n",
    "        if x <= mid:\n",
    "            self.update(p*2,l,mid,x,y,val)\n",
    "        if mid < y:\n",
    "            self.update(p*2+1,mid+1,r,x,y,val)\n",
    "        interval_tree[p] = max(interval_tree[p*2], interval_tree[p*2+1])\n",
    "    \n",
    "    def query(self,p,l,r,x,y):\n",
    "        \"\"\"\n",
    "        查找x,y区间的最大值        \"\"\"        \n",
    "        \n",
    "        if y < l or r < x:\n",
    "            return 0\n",
    "        if x<=l and r<=y:\n",
    "            return self.interval_tree[p]\n",
    "        self.give_lay_to_son(p,l,r)\n",
    "        mid = (l+r)//2\n",
    "        s = 0\n",
    "        if x <= mid:\n",
    "            s = max(s,self.query(p*2,l,mid,x,y))\n",
    "        if mid < y:\n",
    "            s = max(s,self.query(p*2+1,mid+1,r,x,y))\n",
    "        return s\n",
    "\n",
    "class Solution:\n",
    "    def fallingSquares(self, positions: List[List[int]]) -> List[int]:\n",
    "        # # 对于示例一 我们发现 其在区间[1, 2] 上的值应该是 2\n",
    "        # #                      在区间[2, 5] 上的值应该是 5\n",
    "        # #                      在区间[6, 7] 上的值应该是 1\n",
    "        # # 一下子就想到了 线段树\n",
    "\n",
    "        # # n 是 总共 的节点个数\n",
    "        # # 因为数据比较大 不太可能用最大值来充当 n\n",
    "        # # 那么我们就可以用一个去了重的列表 或者是一个 有序集合 来表示\n",
    "        # # 我们的 l 与 r 的定义就是 列表内的索引值 将索引值当成是区间， 就能把区间内的\n",
    "        # # 节点个数的最大值 降至 1000\n",
    "\n",
    "        # # 最大值\n",
    "        # res = 0\n",
    "\n",
    "        # # 更新的操作\n",
    "        # def update(o:int, l:int, r:int, L:int, R:int, add:int) -> None:\n",
    "        #     nonlocal res\n",
    "        #     if l > R or r < L:\n",
    "        #         return   # 不在该区间内\n",
    "        #     if L <= l and r <= R:\n",
    "        #         # 找到了目标区间的子区间 \n",
    "        #         # 对目标区内内的值进行更新操作\n",
    "        #         todo[o] += add\n",
    "        #         res = max(res, todo[o])\n",
    "        #         return\n",
    "        #     # l 和 r 中的某一个值不在范围内\n",
    "        #     mid = (l + r) // 2\n",
    "        #     # 检查是否破坏了原来的区间\n",
    "        #     if todo[o] != 0:\n",
    "        #         todo[o*2] += todo[o]\n",
    "        #         todo[o*2+1] += todo[o]\n",
    "        #         todo[o] = 0\n",
    "        #     if mid >= L : update(o*2, l, mid, L, R, add)\n",
    "        #     if mid < R: update(o*2+1, mid + 1, r, L, R, add)\n",
    "\n",
    "        # # 查询的操作 --- 找到区间 L 和 R 内的最大值\n",
    "        # def quuery(o:int, l:int, r:int, L:int, R:int) -> int:\n",
    "        #     s = 0\n",
    "        #     if l > R or r < L:\n",
    "        #         return   # 不在该区间内\n",
    "        #     if L <= l and r <= R:\n",
    "        #         return todo[o]\n",
    "        #     mid = (l + r) // 2\n",
    "        #     # 检查是否破坏了原来的区间\n",
    "        #     if todo[o] != 0:\n",
    "        #         todo[o*2] += todo[o]\n",
    "        #         todo[o*2+1] += todo[o]\n",
    "        #         todo[o] = 0\n",
    "        #     if mid >= L : s = max(s, quuery(o*2, l, mid, L, R))\n",
    "        #     if mid < R: s = max(s, quuery(o*2+1, mid + 1, r, L, R))\n",
    "        #     return s\n",
    "\n",
    "\n",
    "        # n = len(positions)\n",
    "        # lst = set()\n",
    "        # for i, j in positions:\n",
    "        #     lst.add(i + i + j)  # 保证所有的左右端点都不会超过最大值，保证数据的合理\n",
    "        # lst = list(lst)\n",
    "        # lst.sort()\n",
    "        # length = len(lst)\n",
    "        # todo = [0] * (4 * length)\n",
    "        # for left, add in positions:\n",
    "        #     right = left + add\n",
    "        #     l = bisect_left(lst, left)\n",
    "        #     r = bisect_right(lst, right)\n",
    "        #     h = quuery(1, 0, length, l, r)\n",
    "        #     # update 的更新操作的 add 值 不应该仅仅只是 position 里的增量，我们应该将原来有的\n",
    "        #     # 该区间内的高度进行累加 再更新到该区间\n",
    "        #     update(1, 0, length, l, r, add+h)\n",
    "\n",
    "\n",
    "        n = len(positions)\n",
    "        hashes = [left for left,_ in positions] + [left+side for left,side in positions] \n",
    "        hashes = sorted(list(set(hashes)))\n",
    "        # 用线段树维护x轴区间最大值，记录每个点的高度：比如[1,2]这个方块，会使线段[1,2]闭区间这个线段上的每个高度都变成2\n",
    "        # 落下一个新方块时，查询它的底边所在线段[x,y]的最大高度h，这个方块会落在这个高度h，把新高度h+side插入线段树[x,y]的部分\n",
    "        # 每次插入结束，树根存的高度就是当前最大高度\n",
    "        # 由于数据范围大1 <= lefti <= 108，需要散列化\n",
    "        # 散列化的值有left和right(线段短点)\n",
    "        # print(hashes)\n",
    "        tree_size = len(hashes)\n",
    "        tree = IntervalTree(tree_size)\n",
    "        heights = []\n",
    "        for left,d in positions:\n",
    "            right = left + d \n",
    "            l = bisect_left(hashes,left)\n",
    "            r = bisect_left(hashes,right)\n",
    "            h = tree.query(1,1,tree_size,l+1,r)\n",
    "            tree.update(1,1,tree_size,l+1,r,h+d)\n",
    "            heights.append(tree.interval_tree[1])\n",
    "        return heights\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList \n",
    "class ODT:\n",
    "    def __init__(self):\n",
    "        self.tree=SortedList()##存储(左端点，右端点，值)\n",
    "\n",
    "    def split(self,pos):\n",
    "        i=bisect_left(self.tree,pos,key=lambda x:x[0])\n",
    "        if i==0 or (i<len(self.tree) and self.tree[i][0]==pos):\n",
    "            return i\n",
    "        left,right,val=self.tree[i-1]\n",
    "        if pos<right:\n",
    "            self.tree[i-1][1]=pos\n",
    "            self.tree.add([pos,right,val])\n",
    "        return i\n",
    "\n",
    "    def assign(self,left,right,val):\n",
    "        begin=self.split(left)\n",
    "        end=self.split(right)\n",
    "        base=0\n",
    "        for k in range(begin,end):\n",
    "            tup=self.tree.pop(begin)\n",
    "            base=max(base,tup[2])\n",
    "        val+=base\n",
    "        self.tree.add([left,right,val])\n",
    "        return val\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def fallingSquares(self, positions: List[List[int]]) -> List[int]:\n",
    "        ans=[0]\n",
    "        T=ODT()\n",
    "        for left,size in positions:\n",
    "            ans.append(max(ans[-1],T.assign(left,left+size,size)))\n",
    "        return ans[1:]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def fallingSquares(self, positions: List[List[int]]) -> List[int]:\r\n",
    "        s = set()\r\n",
    "        for i in positions:\r\n",
    "            s.add(i[0])\r\n",
    "            s.add(i[0] + i[1] - 1)\r\n",
    "        s = sorted(list(s))\r\n",
    "\r\n",
    "        idx_map = {}\r\n",
    "        cnt = 1\r\n",
    "        for i in range(len(s)):\r\n",
    "            idx_map[s[i]] = cnt\r\n",
    "            cnt += 1\r\n",
    "\r\n",
    "        tree = [0] * (cnt * 4)\r\n",
    "        mark = [0] * (cnt * 4)\r\n",
    "\r\n",
    "        def push_up(rt):\r\n",
    "            tree[rt] = max(tree[rt << 1], tree[rt << 1 | 1])\r\n",
    "\r\n",
    "        def push_down(rt):\r\n",
    "            if mark[rt]:\r\n",
    "                mark[rt << 1] = max(mark[rt << 1], mark[rt])\r\n",
    "                tree[rt << 1] = max(tree[rt << 1], mark[rt])\r\n",
    "                mark[rt << 1 | 1] = max(mark[rt << 1 | 1], mark[rt])\r\n",
    "                tree[rt << 1 | 1] = max(tree[rt << 1 | 1], mark[rt])\r\n",
    "                mark[rt] = 0\r\n",
    "        \r\n",
    "        def update(rt, cl, cr, ql, qr, val):\r\n",
    "            if ql <= cl and cr <= qr:\r\n",
    "                mark[rt] = max(mark[rt], val)\r\n",
    "                tree[rt] = max(tree[rt], val)\r\n",
    "                return\r\n",
    "            if cr < ql or cl > qr:\r\n",
    "                return\r\n",
    "            \r\n",
    "            mid = (cl + cr) >> 1\r\n",
    "            push_down(rt)\r\n",
    "            update(rt << 1, cl, mid, ql, qr, val)\r\n",
    "            update(rt << 1 | 1, mid + 1, cr, ql, qr, val)\r\n",
    "            push_up(rt)\r\n",
    "        \r\n",
    "        def query(rt, cl, cr, ql, qr):\r\n",
    "            if ql <= cl and cr <= qr:\r\n",
    "                return tree[rt]\r\n",
    "            if cr < ql or cl > qr:\r\n",
    "                return 0\r\n",
    "\r\n",
    "            mid = (cl + cr) >> 1\r\n",
    "            push_down(rt)\r\n",
    "            return max(query(rt << 1, cl, mid, ql, qr), query(rt << 1 | 1, mid + 1, cr, ql, qr))\r\n",
    "\r\n",
    "        ans = []\r\n",
    "        for i in positions:\r\n",
    "            l = i[0]\r\n",
    "            r = i[0] + i[1] - 1\r\n",
    "            h = query(1, 1, cnt, idx_map[l], idx_map[r])\r\n",
    "            update(1, 1, cnt, idx_map[l], idx_map[r], h + i[1])\r\n",
    "            ans.append(query(1, 1, cnt, 1, cnt))\r\n",
    "        \r\n",
    "        return ans\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class IntervalTree:\n",
    "    def __init__(self, size):\n",
    "        self.size = size\n",
    "        self.interval_tree = [0 for _ in range(size*4)]\n",
    "        self.lazys = [0 for _ in range(size*4)]\n",
    "\n",
    "    def give_lay_to_son(self,p,l,r):\n",
    "        interval_tree = self.interval_tree\n",
    "        lazys = self.lazys\n",
    "        if lazys[p] == 0:\n",
    "            return\n",
    "        mid = (l+r)//2\n",
    "        interval_tree[p*2] = lazys[p]\n",
    "        interval_tree[p*2+1] = lazys[p]\n",
    "        lazys[p*2] = lazys[p]\n",
    "        lazys[p*2+1] = lazys[p]\n",
    "        lazys[p] = 0\n",
    "        \n",
    "    def update(self,p,l,r,x,y,val):\n",
    "        \"\"\"\n",
    "        把[x,y]区域全变成val\n",
    "        \"\"\"\n",
    "        if y < l or r < x:\n",
    "            return \n",
    "        interval_tree = self.interval_tree    \n",
    "        lazys = self.lazys        \n",
    "        if x <= l and r<=y:\n",
    "            interval_tree[p] = val\n",
    "            lazys[p] = val\n",
    "            return\n",
    "        self.give_lay_to_son(p,l,r)\n",
    "        mid = (l+r)//2\n",
    "        if x <= mid:\n",
    "            self.update(p*2,l,mid,x,y,val)\n",
    "        if mid < y:\n",
    "            self.update(p*2+1,mid+1,r,x,y,val)\n",
    "        interval_tree[p] = max(interval_tree[p*2], interval_tree[p*2+1])\n",
    "    \n",
    "    def query(self,p,l,r,x,y):\n",
    "        \"\"\"\n",
    "        查找x,y区间的最大值        \"\"\"        \n",
    "        \n",
    "        if y < l or r < x:\n",
    "            return 0\n",
    "        if x<=l and r<=y:\n",
    "            return self.interval_tree[p]\n",
    "        self.give_lay_to_son(p,l,r)\n",
    "        mid = (l+r)//2\n",
    "        s = 0\n",
    "        if x <= mid:\n",
    "            s = max(s,self.query(p*2,l,mid,x,y))\n",
    "        if mid < y:\n",
    "            s = max(s,self.query(p*2+1,mid+1,r,x,y))\n",
    "        return s\n",
    "\n",
    "class Solution:\n",
    "    def fallingSquares(self, positions: List[List[int]]) -> List[int]:\n",
    "        n = len(positions)\n",
    "        hashes = [left for left,_ in positions] + [left+side for left,side in positions] \n",
    "        hashes = sorted(list(set(hashes)))\n",
    "        # 用线段树维护x轴区间最大值，记录每个点的高度：比如[1,2]这个方块，会使线段[1,2]闭区间这个线段上的每个高度都变成2\n",
    "        # 落下一个新方块时，查询它的底边所在线段[x,y]的最大高度h，这个方块会落在这个高度h，把新高度h+side插入线段树[x,y]的部分\n",
    "        # 每次插入结束，树根存的高度就是当前最大高度\n",
    "        # 由于数据范围大1 <= lefti <= 108，需要散列化\n",
    "        # 散列化的值有left和right(线段短点)\n",
    "        # print(hashes)\n",
    "        tree_size = len(hashes)\n",
    "        tree = IntervalTree(tree_size)\n",
    "        heights = []\n",
    "        for left,d in positions:\n",
    "            right = left + d \n",
    "            l = bisect_left(hashes,left)\n",
    "            r = bisect_left(hashes,right)\n",
    "            h = tree.query(1,1,tree_size,l+1,r)\n",
    "            tree.update(1,1,tree_size,l+1,r,h+d)\n",
    "            heights.append(tree.interval_tree[1])\n",
    "        return heights\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fallingSquares(self, positions: List[List[int]]) -> List[int]:\n",
    "\n",
    "        def push_up(o):\n",
    "            tree[o] = max(tree[o*2], tree[o*2+1])\n",
    "        \n",
    "        def push_down(o):\n",
    "            if lazy[o]:\n",
    "                lazy[o*2] = lazy[o]\n",
    "                lazy[o*2+1] = lazy[o]\n",
    "\n",
    "                tree[o*2] = lazy[o]\n",
    "                tree[o*2+1] = lazy[o]\n",
    "                lazy[o] = 0\n",
    "        \n",
    "        def update(o, l, r, L, R, val):\n",
    "            if l >=L and r <= R:\n",
    "                tree[o] = val\n",
    "                lazy[o] = val\n",
    "                return\n",
    "\n",
    "            mid = (l + r) // 2\n",
    "            push_down(o)\n",
    "            if mid >= L:\n",
    "                update(o*2, l, mid, L, R, val)\n",
    "            if mid+1<=R:\n",
    "                update(o*2+1, mid+1, r, L, R, val)\n",
    "            push_up(o)\n",
    "        \n",
    "        def query(o, l, r, L, R):\n",
    "            if l>=L and r <= R:\n",
    "                return tree[o]\n",
    "            mid = (l + r) // 2\n",
    "            push_down(o)\n",
    "            ans = 0\n",
    "            if mid >= L:\n",
    "                ans = max(ans, query(o*2, l, mid, L, R))\n",
    "            if mid+1<=R:\n",
    "                ans = max(ans, query(o*2+1, mid+1, r, L, R))\n",
    "            return ans\n",
    "        \n",
    "        # nums = list()\n",
    "        # for l, w in positions:\n",
    "        #     nums.append(l)\n",
    "        #     nums.append(l+w-1)\n",
    "        \n",
    "        # new_nums = sorted(set(nums))\n",
    "\n",
    "        # n = len(new_nums)\n",
    "        uniques = set()\n",
    "        for l, w in positions:\n",
    "            uniques.add(l)\n",
    "            uniques.add(l + w - 1)\n",
    "        \n",
    "        rank_map = {val: i+1 for i, val in enumerate(sorted(uniques))}\n",
    "        n = len(rank_map)\n",
    "        \n",
    "        tree = [0] * (4*n)\n",
    "        lazy = [0] * (4*n)\n",
    "\n",
    "        ans = []\n",
    "        max_h = 0\n",
    "        for l, w in positions:\n",
    "            r = l + w - 1\n",
    "            i = rank_map[l]\n",
    "            j = rank_map[r]\n",
    "            # i = bisect_left(new_nums, l) + 1\n",
    "            # j = bisect_left(new_nums, r) + 1\n",
    "            q = query(1, 1, n, i, j)\n",
    "            h = q + w\n",
    "            max_h = max(max_h, h)\n",
    "            ans.append(max_h)\n",
    "            update(1, 1, n, i, j, h)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedSet\n",
    "import sys\n",
    "\n",
    "\n",
    "class SegmentTree:\n",
    "    def __init__(self, size):\n",
    "        N = size + 1  # 注意这里先+1\n",
    "        self.is_update = [False] * (N << 2)\n",
    "        self.change = [0] * (N << 2)\n",
    "        self.max_n = [0] * (N << 2)\n",
    "\n",
    "    def update(self, L, R, C, l, r, rt):\n",
    "        if l >= L and r <= R:\n",
    "            self.is_update[rt] = True\n",
    "            self.change[rt] = C\n",
    "            self.max_n[rt] = C\n",
    "            return\n",
    "        mid = (l + r) >> 1\n",
    "        self.push_down(rt, mid-l+1, r-mid)\n",
    "        if mid >= L:\n",
    "            self.update(L, R, C, l, mid, rt << 1)\n",
    "        if mid < R:\n",
    "            self.update(L, R, C, mid+1, r, rt << 1 | 1)\n",
    "        self.push_up(rt)\n",
    "\n",
    "    def push_up(self, rt):\n",
    "        self.max_n[rt] = max(self.max_n[rt << 1], self.max_n[rt << 1 | 1])\n",
    "\n",
    "    def push_down(self, rt, ln, rn):\n",
    "        if self.is_update[rt]:\n",
    "            self.is_update[rt << 1] = True\n",
    "            self.is_update[rt << 1 | 1] = True\n",
    "            self.change[rt << 1] = self.change[rt]\n",
    "            self.change[rt << 1 | 1] = self.change[rt]\n",
    "            self.max_n[rt << 1] = self.change[rt]\n",
    "            self.max_n[rt << 1 | 1] = self.change[rt]\n",
    "            self.is_update[rt] = False\n",
    "\n",
    "    def query(self, L, R, l, r, rt):\n",
    "        if l >= L and r <= R:\n",
    "            return self.max_n[rt]\n",
    "        mid = (l + r) >> 1\n",
    "        self.push_down(rt, mid-l+1, r-mid)\n",
    "        left = -sys.maxsize-1\n",
    "        right = -sys.maxsize-1\n",
    "        if mid >= L:\n",
    "            left = self.query(L, R, l, mid, rt << 1)\n",
    "        if mid < R:\n",
    "            right = self.query(L, R, mid+1, r, rt << 1 | 1)\n",
    "        return max(left, right)\n",
    "\n",
    "class Solution:\n",
    "    def fallingSquares(self, positions: List[List[int]]) -> List[int]:\n",
    "        val_index = self.mapping(positions)\n",
    "        N = len(val_index)\n",
    "        seg = SegmentTree(N)\n",
    "        ans = []\n",
    "        max_n = 0\n",
    "        for pos in positions:\n",
    "            L = val_index[pos[0]]\n",
    "            R = val_index[pos[0] + pos[1] - 1]\n",
    "            height = pos[1]\n",
    "            cur_height = seg.query(L, R, 1, N, 1) + height\n",
    "            max_n = max(max_n, cur_height)\n",
    "            ans.append(max_n)\n",
    "            seg.update(L, R, cur_height, 1, N, 1)\n",
    "        return ans\n",
    "\n",
    "    def mapping(self, positions):\n",
    "        sets = SortedSet()\n",
    "        for pos in positions:\n",
    "            sets.add(pos[0])\n",
    "            sets.add(pos[0] + pos[1] - 1)\n",
    "        val_index = {}\n",
    "        index = 1\n",
    "        for val in sets:\n",
    "            val_index[val] = index\n",
    "            index += 1\n",
    "        return val_index"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fallingSquares(self, positions: List[List[int]]) -> List[int]:\n",
    "        # 离散化处理\n",
    "        index_memory = {}\n",
    "        index_record = []\n",
    "        for position in positions:\n",
    "            index_record.append(position[0])\n",
    "            index_record.append(position[0] + position[1])\n",
    "        index_record.sort()\n",
    "        current = 0\n",
    "        for index in index_record:\n",
    "            if index not in index_memory:\n",
    "                index_memory[index] = current\n",
    "                current += 1\n",
    "        api = SegmentTree(len(index_memory))\n",
    "        ans = []\n",
    "        cur_ans = 0\n",
    "        for position in positions:\n",
    "            index1, index2 = index_memory[position[0]], index_memory[position[0] + position[1]]\n",
    "            previous = api.query(1, index1, index2 - 1)\n",
    "            target_high = previous + position[1]\n",
    "            cur_ans = max(cur_ans, target_high)\n",
    "            ans.append(cur_ans)\n",
    "            api.change_range(1, index1, index2 - 1, target_high)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.mark = self.maxV = self.l = self.r = 0\n",
    "class SegmentTree:\n",
    "    def __init__(self, n):\n",
    "        self.segment_tree = [Node() for _ in range(4 * n)]\n",
    "        self.build_tree(1, 0, n - 1)\n",
    "\n",
    "    def build_tree(self, index, l, r):\n",
    "        self.segment_tree[index].l, self.segment_tree[index].r = l, r\n",
    "        if l == r:\n",
    "            return\n",
    "        mid = (l + r) >> 1\n",
    "        self.build_tree(index * 2, l, mid)\n",
    "        self.build_tree(index * 2 + 1, mid + 1, r)\n",
    "\n",
    "    def query(self, index, l, r):\n",
    "        max1, max2 = 0, 0\n",
    "        if l <= self.segment_tree[index].l and r >= self.segment_tree[index].r:\n",
    "            return self.segment_tree[index].maxV\n",
    "        self.spread(index)\n",
    "        mid = (self.segment_tree[index].l + self.segment_tree[index].r) >> 1\n",
    "        if l <= mid:\n",
    "            max1 = self.query(index * 2, l, r)\n",
    "        if r > mid:\n",
    "            max2 = self.query(index * 2 + 1, l, r)\n",
    "        return max(max1, max2)\n",
    "\n",
    "    def change_range(self, index, l, r, target_high):\n",
    "        if l <= self.segment_tree[index].l and r >= self.segment_tree[index].r:\n",
    "            self.segment_tree[index].maxV = target_high\n",
    "            self.segment_tree[index].mark = target_high\n",
    "            return\n",
    "        self.spread(index)\n",
    "        mid = (self.segment_tree[index].l + self.segment_tree[index].r) >> 1\n",
    "        if l <= mid:\n",
    "            self.change_range(index * 2, l, r, target_high)\n",
    "        if r > mid:\n",
    "            self.change_range(index * 2 + 1, l, r, target_high)\n",
    "        self.segment_tree[index].maxV = max(self.segment_tree[2 * index].maxV, self.segment_tree[2 * index + 1].maxV)\n",
    "\n",
    "    def spread(self, index):\n",
    "        if self.segment_tree[index].mark != 0:\n",
    "            self.segment_tree[2 * index].maxV = self.segment_tree[index].mark\n",
    "            self.segment_tree[2 * index].mark = self.segment_tree[index].mark\n",
    "            self.segment_tree[2 * index + 1].maxV = self.segment_tree[index].mark\n",
    "            self.segment_tree[2 * index + 1].mark = self.segment_tree[index].mark\n",
    "            self.segment_tree[index].mark = 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fallingSquares(self, positions: List[List[int]]) -> List[int]:\n",
    "        # 离散化处理\n",
    "        index_memory = {}\n",
    "        index_record = []\n",
    "        for position in positions:\n",
    "            index_record.append(position[0])\n",
    "            index_record.append(position[0] + position[1])\n",
    "        index_record.sort()\n",
    "        current = 0\n",
    "        for index in index_record:\n",
    "            if index not in index_memory:\n",
    "                index_memory[index] = current\n",
    "                current += 1\n",
    "        api = SegmentTree(len(index_memory))\n",
    "        ans = []\n",
    "        cur_ans = 0\n",
    "        for position in positions:\n",
    "            index1, index2 = index_memory[position[0]], index_memory[position[0] + position[1]]\n",
    "            previous = api.query(1, index1, index2 - 1)\n",
    "            target_high = previous + position[1]\n",
    "            cur_ans = max(cur_ans, target_high)\n",
    "            ans.append(cur_ans)\n",
    "            api.change_range(1, index1, index2 - 1, target_high)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.mark = self.maxV = self.l = self.r = 0\n",
    "class SegmentTree:\n",
    "    def __init__(self, n):\n",
    "        self.segment_tree = [Node() for _ in range(4 * n)]\n",
    "        self.build_tree(1, 0, n - 1)\n",
    "\n",
    "    def build_tree(self, index, l, r):\n",
    "        self.segment_tree[index].l, self.segment_tree[index].r = l, r\n",
    "        if l == r:\n",
    "            return\n",
    "        mid = (l + r) >> 1\n",
    "        self.build_tree(index * 2, l, mid)\n",
    "        self.build_tree(index * 2 + 1, mid + 1, r)\n",
    "\n",
    "    def query(self, index, l, r):\n",
    "        max1, max2 = 0, 0\n",
    "        if l <= self.segment_tree[index].l and r >= self.segment_tree[index].r:\n",
    "            return self.segment_tree[index].maxV\n",
    "        self.spread(index)\n",
    "        mid = (self.segment_tree[index].l + self.segment_tree[index].r) >> 1\n",
    "        if l <= mid:\n",
    "            max1 = self.query(index * 2, l, r)\n",
    "        if r > mid:\n",
    "            max2 = self.query(index * 2 + 1, l, r)\n",
    "        return max(max1, max2)\n",
    "\n",
    "    def change_range(self, index, l, r, target_high):\n",
    "        if l <= self.segment_tree[index].l and r >= self.segment_tree[index].r:\n",
    "            self.segment_tree[index].maxV = target_high\n",
    "            self.segment_tree[index].mark = target_high\n",
    "            return\n",
    "        self.spread(index)\n",
    "        mid = (self.segment_tree[index].l + self.segment_tree[index].r) >> 1\n",
    "        if l <= mid:\n",
    "            self.change_range(index * 2, l, r, target_high)\n",
    "        if r > mid:\n",
    "            self.change_range(index * 2 + 1, l, r, target_high)\n",
    "        self.segment_tree[index].maxV = max(self.segment_tree[2 * index].maxV, self.segment_tree[2 * index + 1].maxV)\n",
    "\n",
    "    def spread(self, index):\n",
    "        if self.segment_tree[index].mark != 0:\n",
    "            self.segment_tree[2 * index].maxV = self.segment_tree[index].mark\n",
    "            self.segment_tree[2 * index].mark = self.segment_tree[index].mark\n",
    "            self.segment_tree[2 * index + 1].maxV = self.segment_tree[index].mark\n",
    "            self.segment_tree[2 * index + 1].mark = self.segment_tree[index].mark\n",
    "            self.segment_tree[index].mark = 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fallingSquares(self, positions: List[List[int]]) -> List[int]:\n",
    "        n = len(positions)\n",
    "        for i in range(n):\n",
    "            positions[i][0] *= 2\n",
    "            positions[i][1] *= 2\n",
    "        \n",
    "        s = set()\n",
    "        for i in range(n):\n",
    "            s.add(positions[i][0])\n",
    "            s.add(positions[i][0] - 1)\n",
    "            s.add(positions[i][0] + 1)\n",
    "            s.add(positions[i][0] + positions[i][1])\n",
    "            s.add(positions[i][0] + positions[i][1] - 1)\n",
    "            s.add(positions[i][0] + positions[i][1] + 1)\n",
    "        L = list(s)\n",
    "        L.sort()\n",
    "        idx_dic = dict()\n",
    "        for i in range(len(L)):\n",
    "            idx_dic[L[i]] = i \n",
    "        \n",
    "        max_L = [0] * (len(L) << 2)\n",
    "        lazy = [0] * (len(L) << 2)\n",
    "\n",
    "        def update(cur_index, l, r, L, R, d):\n",
    "            # [L, R]内的所有数都等于 d\n",
    "            if L <= l and r <= R:\n",
    "                lazy[cur_index] = max(lazy[cur_index], d)\n",
    "                max_L[cur_index] = max(max_L[cur_index], lazy[cur_index])\n",
    "                return\n",
    "            middle = (l + r) // 2\n",
    "            if lazy[cur_index] != 0:\n",
    "                # 如果当前节点上有懒标记，则标记下发\n",
    "                lazy[cur_index * 2] = max(lazy[cur_index * 2], lazy[cur_index])\n",
    "                max_L[cur_index * 2] = max(max_L[cur_index * 2], lazy[cur_index * 2])\n",
    "                lazy[cur_index * 2 + 1] = max(lazy[cur_index * 2 + 1], lazy[cur_index])\n",
    "                max_L[cur_index * 2 + 1] = max(max_L[cur_index * 2 + 1], lazy[cur_index * 2 + 1])\n",
    "                lazy[cur_index] = 0\n",
    "\n",
    "            if L <= middle:\n",
    "                update(cur_index * 2, l, middle, L, R, d)\n",
    "            if R > middle:\n",
    "                update(cur_index * 2 + 1, middle + 1, r, L, R, d)\n",
    "            max_L[cur_index] = max(max_L[cur_index * 2], max_L[cur_index * 2 + 1])\n",
    "            return\n",
    "\n",
    "\n",
    "        def query(cur_index, l, r, L, R):\n",
    "            # 查询区间[L, R]最大值\n",
    "            if L <= l and r <= R:\n",
    "                return max_L[cur_index]\n",
    "            middle = (l + r) // 2\n",
    "            # 注意：如果查询的时候遇到懒标记，也要进行下发\n",
    "            if lazy[cur_index] != 0:\n",
    "                # 如果当前节点上有懒标记，则标记下发\n",
    "                lazy[cur_index * 2] = max(lazy[cur_index * 2], lazy[cur_index])\n",
    "                max_L[cur_index * 2] = max(max_L[cur_index * 2], lazy[cur_index * 2])\n",
    "                lazy[cur_index * 2 + 1] = max(lazy[cur_index * 2 + 1], lazy[cur_index])\n",
    "                max_L[cur_index * 2 + 1] = max(max_L[cur_index * 2 + 1], lazy[cur_index * 2 + 1])\n",
    "\n",
    "            res = 0\n",
    "            if L <= middle:\n",
    "                res = max(res, query(cur_index * 2, l, middle, L, R))\n",
    "            if R > middle:\n",
    "                res = max(res, query(cur_index * 2 + 1, middle + 1, r, L, R))\n",
    "            return res\n",
    "\n",
    "        ans = []\n",
    "        left = positions[0][0]\n",
    "        right = positions[0][0] + positions[0][1]\n",
    "        update(1, 0, len(L) - 1, idx_dic[left], idx_dic[right], positions[0][1])\n",
    "        ans.append(positions[0][1])\n",
    "\n",
    "        for i in range(1, n):\n",
    "            left = positions[i][0]\n",
    "            right = positions[i][0] + positions[i][1]\n",
    "            # print(left, right)\n",
    "            high = query(1, 0, len(L) - 1, idx_dic[left + 1], idx_dic[right - 1])\n",
    "            # print(high)\n",
    "            aim_high = high + positions[i][1]\n",
    "            # print(aim_high)\n",
    "            update(1, 0, len(L) - 1, idx_dic[left], idx_dic[right], aim_high)\n",
    "            ans.append(max(ans[-1], aim_high))\n",
    "        return [high // 2 for high in ans]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    __slots__ = (\"left\", \"right\", \"l\", \"r\", \"mid\", \"lazy\", \"val\")\n",
    "\n",
    "    def __init__(self, l, r):\n",
    "        self.l, self.r = l, r\n",
    "        self.mid = (l + r) // 2\n",
    "        self.left = self.right = None\n",
    "        self.lazy = self.val = 0\n",
    "\n",
    "class SegmentTree:\n",
    "    def __init__(self, l, r):\n",
    "        self.root = Node(l, r)\n",
    "    \n",
    "    def do(self, node, v):\n",
    "        node.val = node.lazy = v\n",
    "    \n",
    "    def pushup(self, node):\n",
    "        node.val = max(node.left.val, node.right.val)\n",
    "    \n",
    "    def pushdown(self, node):\n",
    "        if not node.left:\n",
    "            node.left = Node(node.l, node.mid)\n",
    "        if not node.right:\n",
    "            node.right = Node(1 + node.mid, node.r)\n",
    "        if not node.lazy:\n",
    "            return \n",
    "        self.do(node.left, node.lazy)\n",
    "        self.do(node.right, node.lazy)\n",
    "        node.lazy = 0\n",
    "    \n",
    "    def update(self, node, L, R, v):\n",
    "        if L <= node.l and node.r <= R:\n",
    "            self.do(node, v)\n",
    "            return\n",
    "        self.pushdown(node)\n",
    "        if L <= node.mid:\n",
    "            self.update(node.left, L, R, v)\n",
    "        if R > node.mid:\n",
    "            self.update(node.right, L, R, v)\n",
    "        self.pushup(node)\n",
    "    \n",
    "    def query(self, node, L, R):\n",
    "        if L <= node.l and node.r <= R:\n",
    "            return node.val\n",
    "        self.pushdown(node)\n",
    "        res = 0\n",
    "        if L <= node.mid:\n",
    "            res = self.query(node.left, L, R)\n",
    "        if R > node.mid:\n",
    "            res = max(res, self.query(node.right, L, R))\n",
    "        return res\n",
    "\n",
    "class Solution:\n",
    "    def fallingSquares(self, positions: List[List[int]]) -> List[int]:\n",
    "        U = 2 * 10 ** 8\n",
    "        seg = SegmentTree(0, U)\n",
    "        res = []\n",
    "        for x, y in positions:\n",
    "            mx = seg.query(seg.root, x, x + y - 1)\n",
    "            seg.update(seg.root, x, x + y - 1, mx + y)\n",
    "            res.append(seg.root.val)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    __slots__ = (\"left\", \"right\", \"l\", \"r\", \"mid\", \"lazy\", \"val\")\n",
    "\n",
    "    def __init__(self, l, r):\n",
    "        self.l, self.r = l, r\n",
    "        self.mid = (l + r) // 2\n",
    "        self.left = self.right = None\n",
    "        self.lazy = self.val = 0\n",
    "\n",
    "class SegmentTree:\n",
    "    def __init__(self, l, r):\n",
    "        self.root = Node(l, r)\n",
    "    \n",
    "    def do(self, node, v):\n",
    "        node.val = node.lazy = v\n",
    "    \n",
    "    def pushup(self, node):\n",
    "        node.val = max(node.left.val, node.right.val)\n",
    "    \n",
    "    def pushdown(self, node):\n",
    "        if not node.left:\n",
    "            node.left = Node(node.l, node.mid)\n",
    "        if not node.right:\n",
    "            node.right = Node(1 + node.mid, node.r)\n",
    "        if not node.lazy:\n",
    "            return \n",
    "        self.do(node.left, node.lazy)\n",
    "        self.do(node.right, node.lazy)\n",
    "        node.lazy = 0\n",
    "    \n",
    "    def update(self, node, L, R, v):\n",
    "        if L <= node.l and node.r <= R:\n",
    "            self.do(node, v)\n",
    "            return\n",
    "        self.pushdown(node)\n",
    "        if L <= node.mid:\n",
    "            self.update(node.left, L, R, v)\n",
    "        if R > node.mid:\n",
    "            self.update(node.right, L, R, v)\n",
    "        self.pushup(node)\n",
    "    \n",
    "    def query(self, node, L, R):\n",
    "        if L <= node.l and node.r <= R:\n",
    "            return node.val\n",
    "        self.pushdown(node)\n",
    "        res = 0\n",
    "        if L <= node.mid:\n",
    "            res = self.query(node.left, L, R)\n",
    "        if R > node.mid:\n",
    "            res = max(res, self.query(node.right, L, R))\n",
    "        return res\n",
    "\n",
    "class Solution:\n",
    "    def fallingSquares(self, positions: List[List[int]]) -> List[int]:\n",
    "        U = 2 * 10 ** 8\n",
    "        seg = SegmentTree(0, U)\n",
    "        res = []\n",
    "        for left, sideLength in positions:\n",
    "            mx = seg.query(seg.root, left, left + sideLength - 1)\n",
    "            seg.update(seg.root, left, left + sideLength - 1, mx + sideLength)\n",
    "            res.append(seg.root.val)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fallingSquares(self, positions: List[List[int]]) -> List[int]:\n",
    "        root = SegTree().root\n",
    "        ans = []\n",
    "        for l, s in positions:\n",
    "            t = SegTree.query(root, 0, 10**9, l, l+s-1)\n",
    "            print(t, l, l+s-1, s)\n",
    "            SegTree.update(root, 0, 10**9, l, l+s-1, s+t)\n",
    "            print(root.val)\n",
    "            ans.append(root.val)\n",
    "        return ans\n",
    "\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.left = self.right = None\n",
    "        self.val = self.lazy = 0\n",
    "\n",
    "class SegTree:\n",
    "    def __init__(self):\n",
    "        self.root = Node()\n",
    "\n",
    "    @staticmethod\n",
    "    def pushdown(root):\n",
    "        if root.left == None: root.left = Node()\n",
    "        if root.right == None: root.right = Node()\n",
    "        if root.lazy == 0: return\n",
    "        root.left.val = root.lazy\n",
    "        root.left.lazy = root.lazy\n",
    "        root.right.val = root.lazy\n",
    "        root.right.lazy = root.lazy\n",
    "        root.lazy = 0\n",
    "    \n",
    "    @staticmethod\n",
    "    def update(root, L, R, l, r, val):\n",
    "        if l <= L and R <= r:\n",
    "            root.val = val\n",
    "            root.lazy = val\n",
    "            return\n",
    "        \n",
    "        SegTree.pushdown(root)\n",
    "\n",
    "        mid = (L + R) // 2\n",
    "        if l <= mid: SegTree.update(root.left, L, mid, l, r, val)\n",
    "        if mid < r: SegTree.update(root.right, mid+1, R, l, r, val)\n",
    "        root.val = max(root.left.val, root.right.val)\n",
    "\n",
    "    @staticmethod\n",
    "    def query(root, L, R, l, r):\n",
    "        if l <= L and R <= r:\n",
    "            return root.val\n",
    "        \n",
    "        SegTree.pushdown(root)\n",
    "\n",
    "        ans = 0\n",
    "        mid = (L + R) // 2\n",
    "        if l <= mid: ans = SegTree.query(root.left, L, mid, l, r)\n",
    "        if mid < r: ans = max(ans, SegTree.query(root.right, mid+1, R, l, r))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.val = 0\n",
    "        self.tag = 0\n",
    "\n",
    "class Solution:\n",
    "    def fallingSquares(self, pos: List[List[int]]) -> List[int]:\n",
    "\n",
    "        root = Node()\n",
    "        u = max([i + w for i, w in pos])\n",
    "\n",
    "        def push(o):\n",
    "            if not o.left: o.left = Node()\n",
    "            if not o.right: o.right = Node()\n",
    "            if o.tag == 0:\n",
    "                return\n",
    "            o.left.val = max(o.tag, o.left.val)\n",
    "            o.left.tag = max(o.tag, o.left.tag)\n",
    "            o.right.val = max(o.tag, o.right.val)\n",
    "            o.right.tag = max(o.tag, o.right.tag)\n",
    "            o.tag = 0\n",
    "\n",
    "\n",
    "        def update(o, l, r, L, R, v):\n",
    "            if L <= l and R >= r:\n",
    "                o.val = max(o.val, v)\n",
    "                o.tag = max(o.tag, v)\n",
    "                return\n",
    "            m = (l + r) // 2\n",
    "            push(o)\n",
    "            if L <= m:\n",
    "                update(o.left, l, m, L, R, v)\n",
    "\n",
    "            if R > m:\n",
    "                update(o.right, m + 1, r, L, R, v)\n",
    "\n",
    "            o.val = max(o.left.val, o.right.val)\n",
    "\n",
    "        def query(o, l, r, L, R):\n",
    "            if l > R or r < L:\n",
    "                return 0\n",
    "            if L <= l and R >= r:\n",
    "                return o.val\n",
    "            m = (l + r) // 2\n",
    "            push(o)\n",
    "            ans = 0\n",
    "            if L <= m:\n",
    "                ans = query(o.left, l, m, L, R)\n",
    "            if R > m:\n",
    "                ans = max(ans, query(o.right, m + 1, r, L, R))\n",
    "            return ans\n",
    "\n",
    "        ans = []\n",
    "\n",
    "        for i, w in pos:\n",
    "            h = query(root, 1, u, i, i + w - 1)\n",
    "            update(root, 1, u, i, i + w - 1, h + w)\n",
    "            ans.append(root.val)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.ls = None\n",
    "        self.rs = None\n",
    "        self.val = 0\n",
    "        self.add = 0\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.N = int(1e9+10)\n",
    "        self.root = Node()\n",
    "    def update(self, node, lc, rc,l,r,val):\n",
    "        if l<=lc and rc<=r:\n",
    "            node.val  = val \n",
    "            node.add = val\n",
    "            return\n",
    "        self.pushdown(node)\n",
    "        m = (lc+rc)>>1\n",
    "        if l<=m:\n",
    "            self.update(node.ls, lc,m, l,r,val)\n",
    "        if r>m:\n",
    "            self.update(node.rs, m+1,rc, l,r,val)\n",
    "        self.pushup(node)\n",
    "    def pushdown(self, node):\n",
    "        if not node.ls: node.ls = Node()\n",
    "        if not node.rs: node.rs = Node()\n",
    "        if node.add==0: return\n",
    "        node.ls.val = node.add;\n",
    "        node.rs.val = node.add;\n",
    "        node.ls.add = node.add;\n",
    "        node.rs.add = node.add;\n",
    "        node.add = 0;\n",
    "    def pushup(self, node):\n",
    "        node.val = max(node.ls.val, node.rs.val);\n",
    "    def query(self, node, lc, rc, l, r):\n",
    "        if l<=lc and rc<=r:\n",
    "            return node.val\n",
    "        self.pushdown(node)\n",
    "        m = (lc+rc)>>1\n",
    "        ans = 0\n",
    "        if l<=m:\n",
    "            ans = self.query(node.ls, lc, m, l,r)\n",
    "        if r>m:\n",
    "            ans = max(ans, self.query(node.rs, m+1,rc, l,r))\n",
    "        return ans\n",
    "    def fallingSquares(self, positions: List[List[int]]) -> List[int]:\n",
    "        ans = []\n",
    "        for position in positions:\n",
    "            x = position[0]\n",
    "            h = position[1]\n",
    "            cur = self.query(self.root, 0, self.N-1, x, x + h - 1)\n",
    "            self.update(self.root, 0, self.N-1, x, x + h - 1, cur + h)\n",
    "            ans.append(self.root.val)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "      \n",
    "class Solution:\n",
    "  def fallingSquares(self, positions: List[List[int]]) -> List[int]:\n",
    "    range_min, range_max = 1, 1\n",
    "    for x, y in positions:\n",
    "      range_max = max(range_max, x + y)\n",
    "    st = SegmentTree()\n",
    "    ans = []\n",
    "    for l, sideLength in positions:\n",
    "      r = l + sideLength - 1\n",
    "      cur_max = st.query(st.root, range_min, range_max, l, r)\n",
    "      st.update(st.root, range_min, range_max, l, r, cur_max + sideLength)\n",
    "      ans.append(st.root.val)\n",
    "    return ans\n",
    "\n",
    "class SegmentTreeNode:\n",
    "  def __init__(self) -> None:\n",
    "    self.left = self.right = None\n",
    "    self.val = self.tag = 0\n",
    "\n",
    "class SegmentTree:\n",
    " \n",
    "  def __init__(self) -> None:\n",
    "    self.root = SegmentTreeNode()\n",
    "  \n",
    "  def update(self, node, cl, cr, l, r, d):\n",
    "    if cl >= l and cr <= r:\n",
    "      node.val = d\n",
    "      node.tag = d\n",
    "      return\n",
    "    self.pushDown(node)\n",
    "    mid = cl + cr >> 1\n",
    "    if mid >= l: self.update(node.left, cl, mid, l, r, d)\n",
    "    if mid < r: self.update(node.right, mid + 1, cr, l, r, d)\n",
    "    self.pushUp(node)\n",
    "\n",
    "  def query(self, node, cl, cr, l, r):\n",
    "    if cl >= l and cr <= r: return node.val\n",
    "    self.pushDown(node)\n",
    "    mid = cl + cr >> 1\n",
    "    ans = 0\n",
    "    if mid >= l: ans = self.query(node.left, cl, mid, l, r)\n",
    "    if mid < r: ans = max(ans, self.query(node.right, mid + 1, cr, l, r))\n",
    "    return ans\n",
    "  \n",
    "  def pushDown(self, node):\n",
    "    if not node.left: node.left = SegmentTreeNode()\n",
    "    if not node.right: node.right = SegmentTreeNode()\n",
    "    if not node.tag: return\n",
    "    node.left.val = node.tag\n",
    "    node.left.tag = node.tag\n",
    "    node.right.val = node.tag\n",
    "    node.right.tag = node.tag\n",
    "    node.tag = 0\n",
    "  \n",
    "  def pushUp(self, node):\n",
    "    node.val = max(node.left.val, node.right.val)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fallingSquares(self, positions: List[List[int]]) -> List[int]:\n",
    "        n = 100000001\n",
    "        A = SegTree(n)\n",
    "        root = A.root\n",
    "        ans = []\n",
    "        height = 0\n",
    "        max_num = 0\n",
    "        for pos, h in positions:\n",
    "            height = A.query(root, 0, n - 1, pos, pos + h - 1)\n",
    "            max_num = max(max_num, height + h)\n",
    "            A.update(root, 0, n - 1, pos, pos + h - 1, height + h)\n",
    "            ans.append(max_num)\n",
    "        return ans\n",
    "\n",
    "class Node:\n",
    "\n",
    "    def __init__(self) -> None:\n",
    "        self.val = 0\n",
    "        self.lazy = 0\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "\n",
    "class SegTree:\n",
    "\n",
    "    def __init__(self, n) -> None:\n",
    "        self.n = n\n",
    "        self.root = Node()\n",
    "\n",
    "    def __addnode(self, node):\n",
    "        if node.left == None: node.left = Node()\n",
    "        if node.right == None: node.right = Node()\n",
    "\n",
    "    def __push_up(self, node):\n",
    "        node.val = max(node.left.val, node.right.val)\n",
    "\n",
    "    def __push_down(self, node):\n",
    "        node.left.val = node.val\n",
    "        node.right.val = node.val\n",
    "        node.left.lazy = 1\n",
    "        node.right.lazy = 1\n",
    "        node.lazy = 0\n",
    "    \n",
    "    def update(self, node, lo, hi, left, right, tar):\n",
    "        if left <= lo and right >= hi:\n",
    "            node.val = tar\n",
    "            node.lazy = 1\n",
    "            return\n",
    "        self.__addnode(node)\n",
    "        mid = lo + hi >> 1\n",
    "        if node.lazy != 0:\n",
    "            self.__push_down(node)\n",
    "        if mid >= left:\n",
    "            self.update(node.left, lo, mid, left, right, tar)\n",
    "        if mid < right:\n",
    "            self.update(node.right, mid+1, hi, left, right, tar)\n",
    "        self.__push_up(node)\n",
    "\n",
    "    def query(self, node, lo, hi, left, right):\n",
    "        if left <= lo and right >= hi:\n",
    "            return node.val\n",
    "        self.__addnode(node)\n",
    "        mid = lo + hi >> 1\n",
    "        if node.lazy != 0:\n",
    "            self.__push_down(node)\n",
    "        a = b = 0\n",
    "        if mid >= left:\n",
    "            a = self.query(node.left, lo, mid, left, right)\n",
    "        if mid < right:\n",
    "            b = self.query(node.right, mid+1, hi, left, right)\n",
    "        return max(a, b)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from math import inf\n",
    "      \n",
    "class Solution:\n",
    "  def fallingSquares(self, positions: List[List[int]]) -> List[int]:\n",
    "    range_min, range_max = inf, 1\n",
    "    for x, y in positions:\n",
    "      range_min = min(range_min, x)\n",
    "      range_max = max(range_max, x + y)\n",
    "    st = SegmentTree()\n",
    "    ans = []\n",
    "    for l, sideLength in positions:\n",
    "      r = l + sideLength - 1\n",
    "      cur_max = st.query(st.root, range_min, range_max, l, r)\n",
    "      st.update(st.root, range_min, range_max, l, r, cur_max + sideLength)\n",
    "      ans.append(st.root.val)\n",
    "    return ans\n",
    "\n",
    "class SegmentTreeNode:\n",
    "  def __init__(self) -> None:\n",
    "    self.left = self.right = None\n",
    "    self.val = self.tag = 0\n",
    "\n",
    "class SegmentTree:\n",
    " \n",
    "  def __init__(self) -> None:\n",
    "    self.root = SegmentTreeNode()\n",
    "  \n",
    "  def update(self, node, cl, cr, l, r, d):\n",
    "    if cl >= l and cr <= r:\n",
    "      node.val = d\n",
    "      node.tag = d\n",
    "      return\n",
    "    self.pushDown(node)\n",
    "    mid = cl + cr >> 1\n",
    "    if mid >= l: self.update(node.left, cl, mid, l, r, d)\n",
    "    if mid < r: self.update(node.right, mid + 1, cr, l, r, d)\n",
    "    self.pushUp(node)\n",
    "\n",
    "  def query(self, node, cl, cr, l, r):\n",
    "    if cl >= l and cr <= r: return node.val\n",
    "    self.pushDown(node)\n",
    "    mid = cl + cr >> 1\n",
    "    ans = 0\n",
    "    if mid >= l: ans = self.query(node.left, cl, mid, l, r)\n",
    "    if mid < r: ans = max(ans, self.query(node.right, mid + 1, cr, l, r))\n",
    "    return ans\n",
    "  \n",
    "  def pushDown(self, node):\n",
    "    if not node.left: node.left = SegmentTreeNode()\n",
    "    if not node.right: node.right = SegmentTreeNode()\n",
    "    if not node.tag: return\n",
    "    node.left.val = node.tag\n",
    "    node.left.tag = node.tag\n",
    "    node.right.val = node.tag\n",
    "    node.right.tag = node.tag\n",
    "    node.tag = 0\n",
    "  \n",
    "  def pushUp(self, node):\n",
    "    node.val = max(node.left.val, node.right.val)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "      \n",
    "range_min, range_max = 1, 10 ** 8 + 10 ** 6\n",
    "\n",
    "class Solution:\n",
    "  def fallingSquares(self, positions: List[List[int]]) -> List[int]:\n",
    "    st = SegmentTree()\n",
    "    ans = []\n",
    "    for l, sideLength in positions:\n",
    "      r = l + sideLength - 1\n",
    "      cur_max = st.query(st.root, range_min, range_max, l, r)\n",
    "      st.update(st.root, range_min, range_max, l, r, cur_max + sideLength)\n",
    "      ans.append(st.root.val)\n",
    "    return ans\n",
    "\n",
    "\n",
    "class SegmentTreeNode:\n",
    "  def __init__(self) -> None:\n",
    "    self.left = self.right = None\n",
    "    self.val = self.tag = 0\n",
    "\n",
    "class SegmentTree:\n",
    " \n",
    "  def __init__(self) -> None:\n",
    "    self.root = SegmentTreeNode()\n",
    "  \n",
    "  def update(self, node, cl, cr, l, r, d):\n",
    "    if cl >= l and cr <= r:\n",
    "      node.val = d\n",
    "      node.tag = d\n",
    "      return\n",
    "    self.pushDown(node)\n",
    "    mid = cl + cr >> 1\n",
    "    if mid >= l: self.update(node.left, cl, mid, l, r, d)\n",
    "    if mid < r: self.update(node.right, mid + 1, cr, l, r, d)\n",
    "    self.pushUp(node)\n",
    "\n",
    "  def query(self, node, cl, cr, l, r):\n",
    "    if cl >= l and cr <= r: return node.val\n",
    "    self.pushDown(node)\n",
    "    mid = cl + cr >> 1\n",
    "    ans = 0\n",
    "    if mid >= l: ans = self.query(node.left, cl, mid, l, r)\n",
    "    if mid < r: ans = max(ans, self.query(node.right, mid + 1, cr, l, r))\n",
    "    return ans\n",
    "  \n",
    "  def pushDown(self, node):\n",
    "    if not node.left: node.left = SegmentTreeNode()\n",
    "    if not node.right: node.right = SegmentTreeNode()\n",
    "    if not node.tag: return\n",
    "    node.left.val = node.tag\n",
    "    node.left.tag = node.tag\n",
    "    node.right.val = node.tag\n",
    "    node.right.tag = node.tag\n",
    "    node.tag = 0\n",
    "  \n",
    "  def pushUp(self, node):\n",
    "    node.val = max(node.left.val, node.right.val)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MAX = int(1e8) + int(1e6)\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.root = Node()\n",
    "\n",
    "    def fallingSquares(self, positions: List[List[int]]) -> List[int]:\n",
    "        mx = 0 \n",
    "        ans = []\n",
    "        for i in positions:\n",
    "            p = SegmentTree.query(self.root, 1, MAX, i[0], i[0]+i[1])\n",
    "            SegmentTree.update(self.root, 1, MAX, i[0], i[0]+i[1], i[1], p)\n",
    "            mx = max(mx, SegmentTree.query(self.root, 1, MAX, i[0], i[0]+i[1]))\n",
    "            ans.append(mx)\n",
    "        return ans\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.ln = self.rn = None\n",
    "        self.val = self.add = 0\n",
    "\n",
    "class SegmentTree:\n",
    "    @staticmethod\n",
    "    def query(node: Node, l: int, r: int, s: int, e: int) -> int:\n",
    "        if s <= l and r <= e:\n",
    "            return node.val\n",
    "        SegmentTree.pushdown(node)\n",
    "        m = (l+r)//2\n",
    "        a = 0\n",
    "        if s < m:\n",
    "            a = SegmentTree.query(node.ln, l, m, s, e)\n",
    "        if m < e:\n",
    "            a = max(a, SegmentTree.query(node.rn, m, r, s, e))\n",
    "        return a\n",
    "\n",
    "    @staticmethod\n",
    "    def update(node: Node, l: int, r: int, s: int, e: int, v: int, p: int) -> None:\n",
    "        if s <= l and r <= e:\n",
    "            node.val = v+p\n",
    "            node.add = v+p\n",
    "            return\n",
    "        SegmentTree.pushdown(node)\n",
    "        m = (l+r)//2\n",
    "        if s < m:\n",
    "            SegmentTree.update(node.ln, l, m, s, e, v, p)\n",
    "        if m < e:\n",
    "            SegmentTree.update(node.rn, m, r, s, e, v, p)\n",
    "        SegmentTree.pushup(node)\n",
    "\n",
    "\n",
    "    @staticmethod\n",
    "    def pushdown(node: Node) -> None:\n",
    "        if not node.ln:\n",
    "            node.ln = Node()\n",
    "        if not node.rn:\n",
    "            node.rn = Node()\n",
    "        if not node.add:\n",
    "            return\n",
    "        node.ln.val = node.add\n",
    "        node.ln.add = node.add\n",
    "        node.rn.val = node.add\n",
    "        node.rn.add = node.add\n",
    "        node.add = 0\n",
    "\n",
    "    @staticmethod\n",
    "    def pushup(node: Node) -> None:\n",
    "        node.val = max(node.ln.val, node.rn.val)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    logs = \"\"\n",
    "\n",
    "    def log(self, s):\n",
    "        return\n",
    "        self.logs += s+\"\\n\"\n",
    "\n",
    "    def fallingSquares(self, positions: List[List[int]]) -> List[int]:\n",
    "        ret = [0]*(max([v[0]+v[1] for v in positions]))\n",
    "        max_count = 0\n",
    "        res = []\n",
    "        for x, y in positions:\n",
    "            max_y = max(ret[x:x+y])+y\n",
    "            for i in range(y):\n",
    "                ret[i+x] = max_y\n",
    "            max_count = max(max_count, max_y)\n",
    "            res.append(max_count)\n",
    "        return res\n",
    "\n",
    "    def fallingSquares(self, positions: List[List[int]]) -> List[int]:\n",
    "        max_x = max([v[0]+v[1] for v in positions])\n",
    "        max_count = defaultdict(int)\n",
    "        tmp_count = defaultdict(int)\n",
    "        max_num = 0\n",
    "        ret = []\n",
    "        #\n",
    "\n",
    "        def add(o, v):\n",
    "            tmp_count[o] = v\n",
    "            max_count[o] = v\n",
    "\n",
    "        def down(o):\n",
    "            if tmp_count[o]:\n",
    "                add(o*2, tmp_count[o])\n",
    "                add(o*2+1, tmp_count[o])\n",
    "                tmp_count[o] = 0\n",
    "\n",
    "        def update(o, l, r, L, R, a):\n",
    "            if L <= l and r <= R:\n",
    "                add(o, a)\n",
    "            else:\n",
    "                down(o)\n",
    "                m = (l+r)//2\n",
    "                if L <= m:\n",
    "                    update(o*2, l, m, L, R, a)\n",
    "                if m < R:\n",
    "                    update(o*2+1, m+1, r, L, R, a)\n",
    "                max_count[o] = max(max_count[o*2], max_count[o*2+1])\n",
    "            self.log(f'a[{o} {l} {r} {max_count[o]}]')\n",
    "\n",
    "        def query(o, l, r, L, R):\n",
    "            ret = 0\n",
    "            # self.log(f'p[{o} {l} {r}]')\n",
    "            if L <= l and r <= R:\n",
    "                ret = max_count[o]\n",
    "            else:\n",
    "                down(o)\n",
    "                m = (l+r)//2\n",
    "                if m >= L:\n",
    "                    ret = query(o*2, l, m, L, R)\n",
    "                if m < R:\n",
    "                    ret = max(ret, query(o*2+1, m+1, r, L, R))\n",
    "            self.log(f'q[{o} {l} {r} {ret}]')\n",
    "            return ret\n",
    "        for x, y in positions:\n",
    "            self.log(f'---begin---{x+1}-{x+y}:1-{max_x}')\n",
    "            data = query(1, 1, max_x, x+1, x+y)+y\n",
    "            update(1, 1, max_x, x+1, x+y, data)\n",
    "            max_num = max(max_num, data)\n",
    "            ret.append(max_num)\n",
    "        return ret\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    s = Solution()\n",
    "    for case in [\n",
    "        [[[1, 2], [2, 3], [6, 1]], [2, 5, 5]],\n",
    "        [[[9, 7], [1, 9], [3, 1]], [7, 16, 17]],\n",
    "        [[[100, 100], [200, 100]], [100, 100]]\n",
    "    ]:\n",
    "        s.logs = \"\"\n",
    "        e = s.fallingSquares(*case[:-1])\n",
    "        if e != case[-1]:\n",
    "            print(e, case)\n",
    "            print(s.logs)\n",
    "            break\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fallingSquares(self, positions: List[List[int]]) -> List[int]:\n",
    "        d =  defaultdict(int) \n",
    "        tag=  defaultdict(int) \n",
    "        def pd(s, t, p):\n",
    "            mid = (s + t)>>1\n",
    "            d[2*p] = tag[p]\n",
    "            d[2*p+1] = tag[p]\n",
    "            tag[2*p] = tag[p]\n",
    "            tag[2*p+1] = tag[p]\n",
    "            tag[p] = 0 \n",
    "        def qy(s,t, p, l,r):\n",
    "            if p not in d:\n",
    "                return 0 \n",
    "            if l > t or r < s:\n",
    "                return 0 \n",
    "            if l <= s and t <= r:\n",
    "                return d[p]\n",
    "            mid = (s + t) >> 1\n",
    "            if tag[p]: \n",
    "                pd(s, t, p)\n",
    "            a1,a2= 0,0 \n",
    "            if l<=mid:\n",
    "                a1 = qy(s,mid,2*p, l,r)\n",
    "            if r>=mid+1:\n",
    "                a2 = qy(mid+1,t,2*p+1,l,r)\n",
    "            return max(a1,a2)  \n",
    "        def up(s,t,p,l,r,v):\n",
    "            if l>t or r < s:\n",
    "                return \n",
    "            if l<=s and t <=r:\n",
    "                d[p] = v \n",
    "                tag[p] = v \n",
    "                return \n",
    "            mid = (s + t)>>1\n",
    "           # print(s, t, p, l, r )\n",
    "            if tag[p]:\n",
    "                pd(s,t,p)\n",
    "            if l<=mid:\n",
    "                up(s,mid, 2*p, l,r,v)\n",
    "            if r >=mid+1:\n",
    "                up(mid+1,t, 2*p+1, l,r,v)\n",
    "            d[p] = max(d[2*p], d[2*p+1]) \n",
    "        ans = []\n",
    "        mx = 0 \n",
    "        N = int(1e8)\n",
    "        for l, s in positions:\n",
    "            r = l + s -1\n",
    "            h = qy(1,N, 1, l,r) \n",
    "            #print(l, r, h)\n",
    "            mx = max(mx, h+s) \n",
    "            ans.append(mx) \n",
    "            up(1,N, 1, l, r, h + s)\n",
    "\n",
    "        return ans \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, l, r, height) -> None:\n",
    "        self.r = r\n",
    "        self.l = l\n",
    "        self.height = height\n",
    "        self.lazy = 0\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        \n",
    "class Solution:\n",
    "    def fallingSquares(self, positions: List[List[int]]) -> List[int]:\n",
    "        '''\n",
    "        也可以用一个线段树来query一个区间的最大值\n",
    "        由于每次添加多个数, 所以需要lazy\n",
    "        \n",
    "        整个过程:\n",
    "        当一个方块落下时, query他覆盖的位置的最高值\n",
    "        然后把这个最高值 + 边长 赋值给这个区间(不是加法)\n",
    "        所以对于lazy(lazy一定比当前值大), 直接覆盖当前值就好了\n",
    "        \n",
    "        由于位置的范围是1e8所以用动态开点的方式\n",
    "        '''\n",
    "\n",
    "        height = [0] * (4 * 1100) # 最多1000个位置\n",
    "        lazy = [0] * (4 * 1100)\n",
    "\n",
    "        \n",
    "        def build(l, r):\n",
    "            n = Node(l, r, 0)\n",
    "            return n\n",
    "        \n",
    "        def pushup(o):\n",
    "            # 这个区间的最高值\n",
    "            o.height= max(o.left.height, o.right.height)\n",
    "        \n",
    "        '''\n",
    "        保证子区间的节点存在\n",
    "        '''\n",
    "        def makesure(o):\n",
    "            mid = (o.l + o.r) // 2\n",
    "            if o.left is None:\n",
    "                o.left = Node(o.l, mid, 0)\n",
    "            if o.right is None:\n",
    "                o.right = Node(mid+1, o.r, 0)\n",
    "\n",
    "        '''把lazy传导给下层的子区间\n",
    "        '''    \n",
    "        def pushdown(o):\n",
    "            makesure(o)\n",
    "            o.left.height = o.lazy\n",
    "            o.right.height = o.lazy\n",
    "\n",
    "            o.left.lazy = o.lazy\n",
    "            o.right.lazy = o.lazy\n",
    "            o.lazy = 0\n",
    "            \n",
    "\n",
    "        def query(o, L, R):\n",
    "            if L <= o.l and o.r <= R:\n",
    "                return o.height\n",
    "            \n",
    "            mid = (o.l+o.r)//2\n",
    "            \n",
    "            if o.lazy > 0: # 把这个区间的lazy更新到子区间\n",
    "                pushdown(o)\n",
    "            \n",
    "            # 确保子区间存在\n",
    "            makesure(o)\n",
    "            res = 0 \n",
    "            if L <= mid:\n",
    "                res = max(res, query(o.left, L, R))\n",
    "            if mid < R:\n",
    "                res = max(res, query(o.right, L, R))\n",
    "            \n",
    "            return res\n",
    "        \n",
    "        \n",
    "        def update(o, L, R, h):\n",
    "            '''\n",
    "            将区间的高度设置为h\n",
    "            '''\n",
    "            if L <= o.l and o.r <= R:\n",
    "                o.height = h\n",
    "                o.lazy = h # lazy更新子区间\n",
    "                return\n",
    "            mid = (o.l+o.r)//2\n",
    "\n",
    "            makesure(o)\n",
    "            if L <= mid:\n",
    "                update(o.left, L, R, h)\n",
    "            if mid < R:\n",
    "                update(o.right, L, R, h)\n",
    "            \n",
    "            pushup(o)\n",
    "        \n",
    "\n",
    "        ans = []\n",
    "        root = build(1, 2 * 10 ** 8)\n",
    "        for left, sideLength in positions:\n",
    "            right = left + sideLength - 1\n",
    "            maxh = query(root, left, right)\n",
    "            update(root, left, right, maxh+sideLength)\n",
    "            ans.append(root.height)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, l, r, height) -> None:\n",
    "        self.r = r\n",
    "        self.l = l\n",
    "        self.height = height\n",
    "        self.lazy = 0\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "    \n",
    "    def __repr__(self) -> str:\n",
    "        return f\"[{self.l}, {self.r}]({self.height})\"\n",
    "    \n",
    "    def __str__(self) -> str:\n",
    "        return f\"[{self.l}, {self.r}]({self.height})\"\n",
    "        \n",
    "class Solution:\n",
    "    def fallingSquares(self, positions: List[List[int]]) -> List[int]:\n",
    "        '''\n",
    "        也可以用一个线段树来query一个区间的最大值\n",
    "        由于每次添加多个数, 所以需要lazy\n",
    "        \n",
    "        整个过程:\n",
    "        当一个方块落下时, query他覆盖的位置的最高值\n",
    "        然后把这个最高值 + 边长 赋值给这个区间(不是加法)\n",
    "        所以对于lazy(lazy一定比当前值大), 直接覆盖当前值就好了\n",
    "        \n",
    "        由于位置的范围是1e8所以用动态开点的方式\n",
    "        '''\n",
    "\n",
    "        height = [0] * (4 * 1100) # 最多1000个位置\n",
    "        lazy = [0] * (4 * 1100)\n",
    "\n",
    "        \n",
    "        def build(l, r):\n",
    "            n = Node(l, r, 0)\n",
    "            return n\n",
    "        \n",
    "        def pushup(o):\n",
    "            # 这个区间的最高值\n",
    "            o.height= max(o.left.height, o.right.height)\n",
    "        \n",
    "        def makesure(o):\n",
    "            mid = (o.l + o.r) // 2\n",
    "            if o.left is None:\n",
    "                o.left = Node(o.l, mid, 0)\n",
    "            if o.right is None:\n",
    "                o.right = Node(mid+1, o.r, 0)\n",
    "            \n",
    "        def pushdown(o):\n",
    "            makesure(o)\n",
    "            o.left.height = o.lazy\n",
    "            o.right.height = o.lazy\n",
    "\n",
    "            o.left.lazy = o.lazy\n",
    "            o.right.lazy = o.lazy\n",
    "            o.lazy = 0\n",
    "            \n",
    "\n",
    "        def query(o, L, R):\n",
    "            if L <= o.l and o.r <= R:\n",
    "                return o.height\n",
    "            \n",
    "            mid = (o.l+o.r)//2\n",
    "            \n",
    "            if o.lazy > 0: # 把这个区间的lazy更新到子区间\n",
    "                pushdown(o)\n",
    "            \n",
    "            makesure(o)\n",
    "            res = 0 \n",
    "            if L <= mid:\n",
    "                res = max(res, query(o.left, L, R))\n",
    "            if mid < R:\n",
    "                res = max(res, query(o.right, L, R))\n",
    "            \n",
    "            return res\n",
    "        \n",
    "        \n",
    "        def update(o, L, R, h):\n",
    "            '''\n",
    "            将区间的高度设置为h\n",
    "            '''\n",
    "            if L <= o.l and o.r <= R:\n",
    "                o.height = h\n",
    "                o.lazy = h # lazy更新子区间\n",
    "                return\n",
    "            mid = (o.l+o.r)//2\n",
    "\n",
    "            makesure(o)\n",
    "            if L <= mid:\n",
    "                update(o.left, L, R, h)\n",
    "            if mid < R:\n",
    "                update(o.right, L, R, h)\n",
    "            \n",
    "            pushup(o)\n",
    "        \n",
    "\n",
    "        ans = []\n",
    "        root = build(1, 2 * 10 ** 8)\n",
    "        for left, sideLength in positions:\n",
    "            right = left + sideLength - 1\n",
    "            maxh = query(root, left, right)\n",
    "            update(root, left, right, maxh+sideLength)\n",
    "            ans.append(root.height)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, l, r):\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.l = l\n",
    "        self.r = r\n",
    "        self.mid = (l + r) >> 1\n",
    "        self.v = 0\n",
    "        self.add = 0\n",
    "\n",
    "\n",
    "class SegmentTree:\n",
    "    def __init__(self):\n",
    "        self.root = Node(1, int(1e9))\n",
    "\n",
    "    def modify(self, l, r, v, node=None):\n",
    "        if l > r:\n",
    "            return\n",
    "        if node is None:\n",
    "            node = self.root\n",
    "        if node.l >= l and node.r <= r:\n",
    "            node.v = v\n",
    "            node.add = v\n",
    "            return\n",
    "        self.pushdown(node)\n",
    "        if l <= node.mid:\n",
    "            self.modify(l, r, v, node.left)\n",
    "        if r > node.mid:\n",
    "            self.modify(l, r, v, node.right)\n",
    "        self.pushup(node)\n",
    "\n",
    "    def query(self, l, r, node=None):\n",
    "        if l > r:\n",
    "            return 0\n",
    "        if node is None:\n",
    "            node = self.root\n",
    "        if node.l >= l and node.r <= r:\n",
    "            return node.v\n",
    "        self.pushdown(node)\n",
    "        v = 0\n",
    "        if l <= node.mid:\n",
    "            v = max(v, self.query(l, r, node.left))\n",
    "        if r > node.mid:\n",
    "            v = max(v, self.query(l, r, node.right))\n",
    "        return v\n",
    "\n",
    "    def pushup(self, node):\n",
    "        node.v = max(node.left.v, node.right.v)\n",
    "\n",
    "    def pushdown(self, node):\n",
    "        if node.left is None:\n",
    "            node.left = Node(node.l, node.mid)\n",
    "        if node.right is None:\n",
    "            node.right = Node(node.mid + 1, node.r)\n",
    "        if node.add:\n",
    "            node.left.v = node.add\n",
    "            node.right.v = node.add\n",
    "            node.left.add = node.add\n",
    "            node.right.add = node.add\n",
    "            node.add = 0\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def fallingSquares(self, positions: List[List[int]]) -> List[int]:\n",
    "        ans = []\n",
    "        mx = 0\n",
    "        tree = SegmentTree()\n",
    "        for l, w in positions:\n",
    "            r = l + w - 1\n",
    "            h = tree.query(l, r) + w\n",
    "            mx = max(mx, h)\n",
    "            ans.append(mx)\n",
    "            tree.modify(l, r, h)\n",
    "        return ans\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
